제출 #529096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529096		Gurban	게임 (IOI14_game)	C++17	15 / 100	1 ms	588 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];
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);

    assert(u != 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]){
            m[u][j.first] += j.second;
            m[j.first].erase(v);
            m[j.first][u] += j.second;
        }
        m[v].clear();
        
        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: 0 / 27
• Subtask 3: 0 / 58