oj.uz

Submission #329287

# Submission time Handle Problem Language Result Execution time Memory
329287 2020-11-20T07:36:47 Z gustason Ronald (COCI17_ronald) C++14
120 / 120
 48 ms 4460 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 1005;
vector<int> adj[maxN];
bool visited[maxN];
int arithmeticProgression(int a, int b, int n) {
    return n * (a + b) / 2;
}
int edges, sz;
void dfs(int v) {
    visited[v] = true;
    sz++;
    for(int u : adj[v]) {
        edges++;
        if (!visited[u])
            dfs(u);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int conn = 0;
    bool complete = 1;
    for(int i = 1; i <= n; i++) {
        if (!visited[i]) {
            conn++;
            edges = 0, sz = 0;
            dfs(i);
            edges /= 2;
            if (arithmeticProgression(sz-1, 1, sz-1) != edges) {
                complete = false;
                break;
            }
        }
    }

    if (conn == 2 && complete) {
        cout << "DA\n";
    } else {
        cout << "NE\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

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

Subtask #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 12 ms 1388 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Correct 3 ms 748 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 8 ms 1260 KB Output is correct
3 Correct 31 ms 3308 KB Output is correct
4 Correct 48 ms 4460 KB Output is correct