Submission #282457

#	Time	Username	Problem	Language	Result	Execution time	Memory
282457		shayan_p	Game (IOI14_game)	C++17	100 / 100	530 ms	21752 KiB

game

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

#define F first
#define S second
#define sz(s) (int(s.size()))
#define PB push_back
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 1510, mod = 1e9 + 7, inf = 1e9 + 10;

int ed[maxn][maxn];
int boss[maxn];
vector<int> inside[maxn];
int n;

void initialize(int n){
    ::n = n;
    for(int i = 0; i < n; i++){
	inside[i].PB(i);
	boss[i] = i;
    }	
}
int hasEdge(int u, int v){
    u = boss[u], v = boss[v];
    ed[u][v]++, ed[v][u]++;
    if(ed[u][v] == sz(inside[u]) * sz(inside[v])){
	for(int x : inside[v])
	    boss[x] = u, inside[u].PB(x);
	for(int i = 0; i < n; i++)
	    if(boss[i] == i)
		ed[i][u]+= ed[i][v], ed[u][i]+= ed[v][i];
	return 1;
    }
    return 0;
}

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