oj.uz

Submission #965992

# Submission time Handle Problem Language Result Execution time Memory
965992 2024-04-19T09:02:36 Z 12345678 Ronald (COCI17_ronald) C++17
120 / 120
 38 ms 9544 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int n, edg, m[nx][nx], u, v, vs[nx], cnt;
vector<int> d[nx], c[nx], hd;

void dfs(int u, int p, int h)
{
    c[h].push_back(u);
    vs[u]=1;
    for (auto v:d[u]) if (v!=p&&!vs[v]) dfs(v, u, h);
}

bool complete(int x)
{
    for (auto y:c[x]) for (auto z:c[x]) if (y!=z&&!m[y][z]) return 0;
    return 1;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>edg;
    for (int i=1; i<=edg; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u), m[u][v]=m[v][u]=1;
    for (int i=1; i<=n; i++) if (!vs[i]) cnt++, dfs(i, i, i), hd.push_back(i);
    if (cnt==1&&complete(hd[0])) cout<<"DA";
    else if (cnt==2&&complete(hd[0])&&complete(hd[1])) cout<<"DA";
    else cout<<"NE";
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 1 ms 600 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 7 ms 3912 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 8 ms 3420 KB Output is correct
3 Correct 22 ms 8024 KB Output is correct
4 Correct 38 ms 9544 KB Output is correct