Submission #597960

#	Time	Username	Problem	Language	Result	Execution time	Memory
597960		enerelt14	Game (IOI14_game)	C++14	100 / 100	319 ms	24200 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
int N, p[1500], ch[1500], ed[1500][1500];
void initialize(int n) {
    N=n;
    for (int i=0;i<n;i++){
        p[i]=i;
        ch[i]=1;
    }
}
int find(int x){
    if (p[x]==x)return x;
    return p[x]=find(p[x]);
}
int hasEdge(int u, int v) {
    int x=find(u), y=find(v);
    if (x==y)return 0;
    if (x>y)swap(x, y);
    ed[x][y]++;
    if (ed[x][y]!=ch[x]*ch[y])return 0;
    bool vis[N]={0};
    p[y]=x;
    ch[x]+=ch[y];
    int z;
    for (int i=1;i<=N;i++){
        z=find(i);
        if (z==x || vis[z])continue;
        vis[z]=1;
        ed[min(x, z)][max(x, z)]+=ed[min(y, z)][max(y, z)];
    }
    return 1;
}

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