Submission #715863

#	Time	Username	Problem	Language	Result	Execution time	Memory
715863		bin9638	Game (IOI14_game)	C++17	100 / 100	496 ms	17548 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,cnt[N][N];
bitset<N>bit[N],f[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);
        for(int i=0;i<n;i++)
        {
            bit[i].reset();
            f[i].reset();
            bit[i][i]=1;
            for(int j=0;j<n;j++)
                f[i][j]=1;
            for(int j=0;j<n;j++)
                cnt[i][j]=1;
        }
    }

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

    bool update(int u,int v)
    {
        int i=u,j=v;
        u=root(u);
        v=root(v);
        //cout<<cnt[u][j]<<" "<<cnt[v][i]<<endl;
        cnt[u][j]--;
        if(cnt[u][j]==0)
            f[u][j]=0;
        cnt[v][i]--;
        if(cnt[v][i]==0)
            f[v][i]=0;
      //  cout<<cnt[u][j]<<" "<<cnt[v][i]<<endl;
      //  cout<<u<<" "<<v<<endl;
        bitset<N>tmp=(f[u]&bit[v]);
      //  for(int i=0;i<n;i++)cout<<tmp[i]<<" ";cout<<endl;
        if(tmp.count()>0)
        {
            return 0;
        }
        if(lab[u]>lab[v])
            swap(u,v);
        lab[u]+=lab[v];
        lab[v]=u;
        bit[u]|=bit[v];
        for(int t=0;t<n;t++)
        {
            cnt[u][t]+=cnt[v][t];
            if(cnt[u][t]>0)
                f[u][t]=1;
        }
        return 1;
    }
}T;


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

void initialize(int cc)
{
    n=cc;
        memset(cnt,0,sizeof(cnt));
    T.init();
    //cout<<cnt[0][1]<<endl
    #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: 58 / 58