Submission #529108

#	Time	Username	Problem	Language	Result	Execution time	Memory
529108		Gurban	Game (IOI14_game)	C++17	100 / 100	611 ms	27204 KiB

game

#include "bits/stdc++.h"
#include "game.h"
using namespace std;
 
using ll = long long;
 
const int maxn=1505;
int p[maxn],sz[maxn];
unordered_map<int,int>m[maxn];
 
void initialize(int n) {
    for(int i = 0;i < n;i++){
        p[i] = i;
        sz[i] = 1;
    }
}
 
int ata(int x){
    if(p[x] == x) return x;
    return p[x] = ata(p[x]);
}
 
int hasEdge(int u, int v) {
    u = ata(u);
    v = ata(v);
 
    if((int)m[u].size() < (int)m[v].size()) swap(u,v);
    
    int now = 0;
    if(m[v].find(u) != m[v].end()) now = m[v][u];
 
    if(now == sz[u] * sz[v] - 1){
        for(auto j : m[v]){
            if(j.first == u) continue;
            m[u][j.first] += j.second;
            if(m[j.first].find(v) != m[j.first].end()) m[j.first].erase(v);
            m[j.first][u] += j.second;
        }
        m[v].clear();
        if(m[u].find(v) != m[u].end()) m[u].erase(v);
 
        p[v] = u;
        sz[u] += sz[v];
        sz[v] = 0;
        
        return 1;
    }
    m[u][v]++;
    m[v][u]++;
    return 0;
}

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