Submission #599597

#	Time	Username	Problem	Language	Result	Execution time	Memory
599597		Lucpp	Game (IOI14_game)	C++17	100 / 100	394 ms	25164 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> asked;
vector<int> cnt;
vector<int> par;

int find(int x){
    if(x == par[x]) return par[x];
    else return par[x] = find(par[x]);
}

void initialize(int n_) {
    n = n_;
    par.resize(n);
    for(int i = 0; i < n; i++) par[i] = i;
    cnt.assign(n, 1);
    asked.assign(n, vector<int>(n, 0));
}

int hasEdge(int u, int v) {
    u = find(u);
    v = find(v);
    asked[u][v]++;
    asked[v][u]++;
    if(asked[u][v] != cnt[u]*cnt[v]) return 0;
    par[v] = u;
    cnt[u] += cnt[v];
    for(int i = 0; i < n; i++){
        asked[u][i] += asked[v][i];
        asked[i][u] += asked[i][v];
    }
    return 1;
}

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