Submission #128482

#	Time	Username	Problem	Language	Result	Execution time	Memory
128482		kjp4155	Game (IOI14_game)	C++17	42 / 100	1070 ms	1216 KiB

game

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

int pa[1600];
int sz[1600];
int N;
vector<int> E[1600];
set<int> D[1600];
bool vis[1600];

int find(int x){
    if( x == pa[x] ) return x;
    return pa[x] = find(pa[x]);
}
void uni(int a, int b){ 
    a = find(a); b = find(b);
    if( a == b ) return;
    sz[a] += sz[b];
    pa[b] = a;
}

void initialize(int n) {
    for(int i=0;i<n;i++) pa[i] = i, sz[i] = 1;
    N = n;
}

int dfs(int x){
    int ret = 1;
    vis[x] = 1;
    for(int i=0;i<N;i++) if( !vis[i] && D[x].count(i) == 0 ){
        ret += dfs(i);
    }
    return ret;
}

int hasEdge(int u, int v) {
    // 1. u,v 가 이미 같은 component면 잇는다
    if( find(u) == find(v) ){
        E[u].push_back(v); E[v].push_back(u);
        return 1;
    }
    
    // 2. (u,v)를 잇고 나머지를 다 끊어도 connected면 끊는다
    if( sz[find(u)] + sz[find(v)] == N ){
        D[u].insert(v); D[v].insert(u);
        return 0;
    }
    for(int i=0;i<N;i++) vis[i] = 0;
    // 3. (u,v)를 끊고 나머지를 다 이어도 disconnected면 잇는다
    D[u].insert(v); D[v].insert(u);
    if( dfs(1) < N ){
        D[u].erase(v); D[v].erase(u);
        E[u].push_back(v); E[v].push_back(u);
        uni(u,v);
        return 1;
    }


    // 4. 다 아니면 끊는다 (random 으로 바꿔볼만 한가?)
    //E[u].push_back(v); E[v].push_back(u);
    //uni(u,v);
    D[u].insert(v); D[v].insert(u);
    return 0;
}

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