oj.uz

Submission #963875

# Submission time Handle Problem Language Result Execution time Memory
963875 2024-04-16T00:30:21 Z shezitt Ronald (COCI17_ronald) C++14
120 / 120
 99 ms 16720 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <numeric>

using namespace std;

using ll = long long;
#define int ll
#define vi vector<int>
#define fore(i, a, b) for(int i=a; i<b; ++i)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pb push_back

const int N = 1010;

vi adj[N];
int adjM[N][N];
bool vis[N];

vi list;

void dfs(int i){
    vis[i] = 1;
    list.pb(i);
    for(int v : adj[i]){
        if(vis[v]) continue;
        dfs(v);
    }
}

signed main(){
    int n, m;
    cin >> n >> m;

    fore(i, 0, m){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        adjM[u][v] = adjM[v][u] = 1;
    }

    // at most two complete components

    bool ok = 1;
    int cnt = 0;

    fore(i, 1, n+1){
        if(vis[i]) continue;
        list.clear();
        cnt++;
        dfs(i);
        fore(j, 0, sz(list)){
            fore(k, j+1, sz(list)){
                ok &= adjM[list[j]][list[k]];
            }
        }
    }

    if(ok && cnt <= 2){
        cout << "DA";
    } else {
        cout << "NE";
    }

    cout << endl;

}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #5
15.0 / 15.0

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

Subtask #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1628 KB Output is correct
2 Correct 22 ms 6492 KB Output is correct
3 Correct 9 ms 2908 KB Output is correct
4 Correct 6 ms 2884 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1880 KB Output is correct
2 Correct 15 ms 5856 KB Output is correct
3 Correct 62 ms 14300 KB Output is correct
4 Correct 99 ms 16720 KB Output is correct