Submission #1102106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102106		alexander707070	Game (IOI14_game)	C++14	100 / 100	532 ms	26756 KiB

game

#include<bits/stdc++.h>
#include "game.h"

#define MAXN 1507
using namespace std;

int edge[MAXN][MAXN],n;
unordered_set<int> tree[MAXN];

vector<int> a,b,w;

void comp(int x,int p){
    w.push_back(x);

    for(int i:tree[x]){
        if(i==p)continue;
        comp(i,x);
    }
}

void initialize(int N) {
    n=N;

    for(int i=1;i<=n;i++)tree[i].clear();

    for(int i=1;i<=n;i++){
        for(int f=1;f<=n;f++){
            edge[i][f]=0;
        }
    }

    for(int i=2;i<=n;i++){
        int s=rand()%(i-1)+1;

        tree[i].insert(s);
        tree[s].insert(i);
    }
}

int hasEdge(int u, int v){
    u++; v++;

    if(tree[u].find(v)==tree[u].end()){
        edge[u][v]=edge[v][u]=1;
        return 0;
    }

    w.clear();
    comp(u,v); a=w;

    w.clear();
    comp(v,u); b=w;

    for(int i:a){
        for(int f:b){
            if(edge[i][f]!=0)continue;
            if(i==u and f==v)continue;

            tree[u].erase(v);
            tree[v].erase(u);

            tree[i].insert(f);
            tree[f].insert(i);

            edge[u][v]=edge[v][u]=1;
            return 0;
        }
    }

    edge[u][v]=edge[v][u]=2;
    return 1;
}

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