Submission #336571

#	Time	Username	Problem	Language	Result	Execution time	Memory
336571		bigDuck	Game (IOI14_game)	C++14	100 / 100	550 ms	25452 KiB

game

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#include "game.h"


int s[1510][1510];
int p[1510];
int sz[1510];
int n;

void initialize(int N) {
n=N;
for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
        s[i][j]=1; s[j][i]=1;
    }
    p[i]=i;
}


}


int root(int u){
    int cr=u;
    vector<int> v;
   // cout<<cr<<" ";
   // cout<<"z"<<flush;
    while(p[cr]!=cr){
        v.pb(cr);
        cr=p[cr];
      //  cout<<"y"<<flush;
    }
    //cout<<"z"<<flush;
    if(!v.empty()){
          //  cout<<"z"<<flush;
    for(auto nod:v){
        p[nod]=cr;
    }
    }
    return cr;
}



void unite(int u, int v){
int ru=root(u), rv=root(v);


if(sz[rv]>sz[ru]){
    p[ru]=rv; sz[rv]+=sz[ru];
}
else{
    p[rv]=ru; sz[ru]+=sz[rv];
}

}




int hasEdge(int u, int v) {

    int ru=root(u), rv=root(v);
    if(ru==rv){
        return 0;
    }
    //cout<<"x"<<flush;
    if(s[ru][rv]==1){
        int w=( (sz[ru]>=sz[rv])?(ru):(rv) );
        for(int i=0; i<n; i++){
            if( (i==ru)||(i==rv) ){continue;}
            s[w][i]=s[i][w]=s[ru][i]+s[rv][i];
        }
        //cout<<"x"<<flush;
        unite(ru, rv);
        return 1;
    }
    else{
        s[ru][rv]--; s[rv][ru]--;
        return 0;
    }

}

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