Submission #371621


Source Code Expand

#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <cstdio>
#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;


const int MN = 110000;

int n;
int l[MN], r[MN];
int deg[MN];
vector<int> g[MN];
bool visit[MN];
int color[MN];

void dfs(int p, int c) {
    if (visit[p]) return;
    visit[p] = true;
    color[p] = c;
    for (int d: g[p]) {
        dfs(d, 1-c);
    }
}

int main() {
    cin >> n;
    assert(n >= 3);
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        l[i] = a; r[i] = b;
        g[a].push_back(b);
        g[b].push_back(a);
        deg[a]++;
        deg[b]++;
    }
    int mi = 100000;
    for (int i = 0; i < n; i++) {
        mi = min(mi, deg[i]);
    }
    assert(mi <= 2);
    dfs(0, 0);
    int ma = 0;
    for (int i = 0; i < n; i++) {
        assert(visit[i]);
        if (color[l[i]] != color[r[i]]) {
            ma++;
        }
    }
    assert(ma >= n-1);
    printf("%d %d\n", mi, ma);
    return 0;
}

Submission Info

Submission Time
Task C - 最小カットと最大カット
User yosupo
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1190 Byte
Status AC
Exec Time 178 ms
Memory 11300 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 29
Set Name Test Cases
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 30 ms 3352 KB
scrambled_01.txt AC 31 ms 3296 KB
scrambled_02.txt AC 28 ms 3484 KB
scrambled_03.txt AC 175 ms 11300 KB
scrambled_04.txt AC 178 ms 11300 KB
scrambled_05.txt AC 119 ms 8228 KB
scrambled_06.txt AC 85 ms 6364 KB
scrambled_07.txt AC 166 ms 10588 KB
scrambled_08.txt AC 70 ms 5796 KB
scrambled_09.txt AC 86 ms 6556 KB
scrambled_10.txt AC 153 ms 8472 KB
scrambled_11.txt AC 76 ms 5280 KB
scrambled_12.txt AC 127 ms 7452 KB
scrambled_13.txt AC 125 ms 7200 KB
scrambled_14.txt AC 168 ms 8104 KB
scrambled_15.txt AC 130 ms 6696 KB
scrambled_16.txt AC 76 ms 5156 KB
scrambled_17.txt AC 76 ms 5160 KB
scrambled_18.txt AC 167 ms 8224 KB
scrambled_19.txt AC 38 ms 3744 KB
scrambled_20.txt AC 114 ms 6432 KB
scrambled_21.txt AC 77 ms 5152 KB
scrambled_22.txt AC 125 ms 6692 KB
scrambled_23.txt AC 85 ms 5412 KB
scrambled_24.txt AC 80 ms 5288 KB
scrambled_25.txt AC 96 ms 5792 KB
scrambled_26.txt AC 83 ms 5280 KB
scrambled_27.txt AC 112 ms 6308 KB
scrambled_28.txt AC 105 ms 6056 KB