Submission #715860

#	Time	Username	Problem	Language	Result	Execution time	Memory
715860		bin9638	Game (IOI14_game)	C++17	42 / 100	1091 ms	11012 KiB

game

#include<bits/stdc++.h>

#ifndef SKY
#include "game.h"
#endif // SKY

using namespace std;
#define N 1510
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>

int n,ktr[N][N];

struct DSU
{
    int lab[N];
    vector<int>lis[N];

    void init()
    {
        memset(lab,-1,sizeof(lab));
        for(int i=0;i<n;i++)
            lis[i].pb(i);
    }

    int root(int u)
    {
        if(lab[u]<0)
            return u;
        return(lab[u]=root(lab[u]));
    }

    bool update(int u,int v)
    {
        u=root(u);
        v=root(v);
        int cnt=0;
        for(auto x:lis[u])
            for(auto y:lis[v])
                cnt+=(ktr[x][y]==0);
        if(cnt>1)
            return 0;
        if(lab[u]>lab[v])
            swap(u,v);
        lab[u]+=lab[v];
        lab[v]=u;
        for(auto y:lis[v])
            lis[u].pb(y);
        return 1;
    }
}T;


int hasEdge(int u, int v)
{
    int res=T.update(u,v);
    ktr[u][v]=ktr[v][u]=1;
    #ifdef SKY
    if(res==1)cout<<"YES\n";else cout<<"NO\n";
    #endif // SKY
    return res;
}

void initialize(int cc)
{
    n=cc;
    T.init();
    memset(ktr,0,sizeof(ktr));
    #ifdef SKY
    for(int i=1;i<=n*(n-1)/2;i++)
    {
        int u,v;
        cin>>u>>v;
        int cc=hasEdge(u,v);
    }
    #endif // SKY
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    initialize(n);
    return 0;
}
#endif // SKY

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58