제출 #972997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972997		AndrijaM	Ronald (COCI17_ronald)	C++14	120 / 120	24 ms	2256 KiB

ronald

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15
• Subtask 7: 15 / 15
• Subtask 8: 15 / 15