oj.uz

Submission #246402

# Submission time Handle Problem Language Result Execution time Memory
246402 2020-07-09T07:05:53 Z NONAME Ronald (COCI17_ronald) C++14
105 / 120
 47 ms 2424 KB 
#include  <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e4;

int pr[N], cnt[N], e[N];

int f(int x) { return (x == pr[x]) ? x : pr[x] = f(pr[x]); }

int main() {
    fast_io;

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; ++i)
        pr[i] = i, cnt[i] = 1, e[i] = 0;

    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;

        if (f(v) == f(u)) ++e[f(v)];
            else {
                cnt[f(v)] += cnt[f(u)];
                e[f(v)] += e[f(u)] + 1;
            }

        pr[f(u)] = f(v);
    }

    for (int i = 0; i < n; ++i)
        if ((cnt[f(i)] * (cnt[f(i)] - 1) / 2) != e[f(i)])
            return void(cout << "NE\n"), 0;
    cout << "DA\n";
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 8 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 11 ms 640 KB Output is correct
3 Correct 33 ms 1656 KB Output is correct
4 Correct 47 ms 2424 KB Output is correct