oj.uz

Submission #972997

# Submission time Handle Problem Language Result Execution time Memory
972997 2024-05-01T11:49:19 Z AndrijaM Ronald (COCI17_ronald) C++14
120 / 120
 24 ms 2256 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const long long maxn = 1000 + 5;
const long long logn=25;
const long long mod=1e9+7;

int idx[maxn];
int s[maxn];
int n,m;
int kol;

int find_root(int x)
{
    while(x!=idx[x])
    {
        idx[x]=idx[idx[x]];
        x=idx[x];
    }
    return x;
}

bool is_in_u(int a,int b)
{
    if(find_root(a)==find_root(b))return true;
    return false;
}

void u2e(int i,int j)
{
    int idx_i=find_root(i);
    int idx_j=find_root(j);
    if(s[idx_i]>=s[idx_j])
    {
        s[idx_i]+=s[idx_j];
        idx[idx_j]=idx[idx_i];
    }
    else
    {
        s[idx_j]+=s[idx_i];
        idx[idx_i]=idx[idx_j];
    }
    kol--;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
   /// freopen("conexidad.in", "r", stdin);
   /// freopen("conexidad.out", "w", stdout);
    cin>>n>>m;
    kol=n;
    for(int i=0;i<=n;i++)
    {
        idx[i]=i;
        s[i]=1;
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(!is_in_u(a,b))
        {
            u2e(a,b);
        }
    }
    if(kol==2)
    {
        int V=find_root(1);
        int sum=s[V];
        if(m==(n*(n-1)/2)-sum*(n-sum))
        {
            cout<<"DA"<<endl;
            return 0;
        }
    }
    cout<<"NE"<<endl;
    return 0;
}

Subtask #1
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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 #3
15.0 / 15.0

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

Subtask #5
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 0 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 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 #7
15.0 / 15.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 16 ms 1624 KB Output is correct
4 Correct 24 ms 2256 KB Output is correct