Submission #287039

#	Time	Username	Problem	Language	Result	Execution time	Memory
287039		Atill83	Game (IOI14_game)	C++14	100 / 100	789 ms	25336 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int adj[1501][1501];
int par[1501];
unordered_set<int> comps;
int N;
int find_set(int a){
    if(a == par[a]) return a;
    return par[a] = find_set(par[a]);
}
void merge(int a, int b){
    comps.erase(b);
    par[b] = a;
    adj[a][b] = 1;
    adj[b][a] = 1;
    for(int i = 0; i < N; i++){
        if(i == a) continue;
        if(adj[b][i]){
            adj[a][i] = 1;
            adj[i][a] = 1;
        }
    }
}



void initialize(int n) {
    N = n;
    memset(adj, -1, sizeof(adj));
    for(int i = 0; i < n; i++){ adj[i][i] = 0; par[i] = i; comps.insert(i);}
}

int hasEdge(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if(u == v) return 0;
    for(int i: comps){
        if(adj[i][u] != 0 && adj[i][v] != 0){
            adj[u][v] = 0;
            adj[v][u] = 0;
             return 0;
        }
    }
    merge(u, v);
    return 1;
}

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