oj.uz

Submission #1074344

# Submission time Handle Problem Language Result Execution time Memory
1074344 2024-08-25T09:55:41 Z FIFI_cpp Ronald (COCI17_ronald) C++17
120 / 120
 67 ms 6280 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<pair<int,int>,int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
//ifstream fin ("egale.in");
//ofstream fout ("egale.out");
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
// encouraging cat
const int INF = 1000000007;
const int mod = 1000000007;
vector<int> parent;
vector<int> sizes;
int find_parent(int x)
{
    if (parent[x] == x)
        return x;
    return parent[x] = find_parent(parent[x]);
}
void merge(int a,int b)
{
    a = find_parent(a);
    b = find_parent(b);
    if (a == b)
        return;
    if (sizes[b] > sizes[a])
        swap(a,b);
    parent[b] = a;
    sizes[a] += sizes[b];
}
bool connected(int a,int b)
{
    if (find_parent(a) == find_parent(b))
        return true;
    return false;
}
int32_t main() {
    int n,m;
    cin >> n >> m;
    vector<vector<int>> adj(n,vector<int> (n,0));
    parent.resize(n);
    sizes.resize(n);
    for (int i = 0;i < n;i++)
    {
        parent[i] = i;
        sizes[i] = 1;
    }
    for (int i = 0;i < m;i++)
    {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        merge(a,b);
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
    set<int> diff;
    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < n;j++)
        {
            if (i == j)
                continue;
            if (!adj[i][j] && find_parent(i) == find_parent(j))
            {
                cout << "NE\n";
                return 0;
            }
        }
        diff.insert(find_parent(i));
    }
    if (diff.size() <= 2)
    {
        cout << "DA\n";
    }
    else
    {
        cout << "NE\n";
    }
    return 0;
}

Compilation message

ronald.cpp:32:9: warning: "/*" within comment [-Wcomment]
   32 | /*   /\_/\
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 432 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 424 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 348 KB Output is correct
3 Correct 1 ms 348 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 0 ms 348 KB Output is correct
3 Correct 1 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 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 #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 16 ms 1896 KB Output is correct
3 Correct 6 ms 860 KB Output is correct
4 Correct 5 ms 908 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 10 ms 1628 KB Output is correct
3 Correct 55 ms 5524 KB Output is correct
4 Correct 67 ms 6280 KB Output is correct