Submission #1062298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062298		Vedant18	Game (IOI14_game)	C++14	100 / 100	243 ms	27220 KiB

game

#include<bits/stdc++.h>
using namespace std;
int n;
    vector<int>par;
    vector<int>sz;
    vector<vector<int>>dn;
void initialize(int inp){
    n=inp;
    par.resize(n);
    sz.resize(n);
    dn.resize(n);
    for(int i=0;i<n;i++){
        par[i]=i;
        sz[i]=1;
        dn[i].resize(n);
    }
}
int hasEdge(int a, int b){
    function<int(int)> pr=[&](int v){
        if(par[v]==v){
            return v;
        } 
        return par[v]=pr(par[v]);
    };
        a=pr(a);
        b=pr(b);
        if((dn[a][b]+1)==sz[a]*sz[b]){
            if(sz[a]<sz[b]){
                swap(a,b);
            }
            par[b]=a;
            sz[a]+=sz[b];
            for(int i=0;i<n;i++){
                dn[a][i]+=dn[b][i];
                dn[i][a]=dn[a][i];
            }
            return 1;
        }
        else{
            dn[a][b]++;
            dn[b][a]++;
            return 0;
        }
}

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