Submission #136173

#	Time	Username	Problem	Language	Result	Execution time	Memory
136173		OptxPrime	Game (IOI14_game)	C++11	100 / 100	515 ms	25360 KiB

game

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include<queue>
#include<map>
#include<string.h>

using namespace std;
#define pb push_back
#define mp make_pair
#define fb find_best

    int n;
    int rank1[1510],p[1510];
  //  map<int,int> d;
  int d[1510][1510];
  int sz[1510];

    int findset( int x )
    {
        if( p[x]!=x ) return p[x]=findset( p[x] );
        else return x;
    }
    void uniset( int x, int y )
    {
        //if( issameset( x,y ) ) return;

        int a=findset(x);
        int b=findset(y);
        if( rank1[a] > rank1[b] ){
            p[b]=a;
            for( int i=0;i<n;i++ ){
                d[a][i]+=d[b][i];
                d[i][a]+=d[i][b];
            } 
            sz[a]+=sz[b];
        }
        else{
            p[a]=b;
            for(int i=0;i<n;i++){
                 d[b][i]+=d[a][i];
                 d[i][b]+=d[i][a];
            }
            sz[b]+=sz[a];
            if( rank1[a]==rank1[b] ) rank1[b]++;
        }
    }

    void initialize(int N)
    {
        n=N;
        for( int i=0;i<n;i++ ){
            rank1[i]=0;
            p[i]=i;
            sz[i]=1;
            for( int j=0;j<n;j++ ) d[i][j]=0;
        }
    }
    int hasEdge(int u, int v)
    {
        int a=findset(u);
        int b=findset(v);
        d[a][b]++;
        d[b][a]++;
        if( d[a][b]== sz[a]*sz[b] ){
                uniset( a,b );
            return 1;
        }
        else return 0;
    }

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