제출 #1023604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023604		HappyCapybara	게임 (IOI14_game)	C++17	0 / 100	1 ms	348 KiB

game

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

int N;
vector<int> w, p;
vector<vector<int>> am;

int find(int a){
    if (p[a] == a) return a;
    return p[a] = find(p[a]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a == b) return;
    p[a] = b;
}

void initialize(int n){
    N = n;
    w.resize(N, N-1);
    p.resize(N);
    for (int i=0; i<N; i++) p[i] = i;
    am.resize(N, vector<int>(N, 1));
    for (int i=0; i<N; i++) am[i][i] = 0;
    am[0][1] = 0;
    am[1][0] = 0;
    w[0]--;
    w[1]--;
}

void connect(int t, int u, int v){
    if (t == 0){
        am[u][v] = 0;
        am[v][u] = 0;
        w[u]--;
        w[v]--;
        if (w[u] == 1 || (w[u] == 2 && u >= 2)){
            for (int i=0; i<N; i++){
                if (am[u][i] == 1) connect(1, u, i);
            }
        }
        if (w[v] == 1 || (w[v] == 2 && v >= 2)){
            for (int i=0; i<N; i++){
                if (am[v][i] == 1) connect(1, v, i);
            }
        }
        return;
    }
    am[u][v] = 2;
    am[v][u] = 2;
    if (find(u) == find(0)){
        for (int i=0; i<N; i++){
            if (find(i) == find(v)){
                for (int j=0; j<N; j++){
                    if (find(j) == find(1)) connect(0, i, j);
                }
            }
        }
    }
    if (find(u) == find(1)){
        for (int i=0; i<N; i++){
            if (find(i) == find(v)){
                for (int j=0; j<N; j++){
                    if (find(j) == find(0)) connect(0, i, j);
                }
            }
        }
    }
    if (find(v) == find(0)){
        for (int i=0; i<N; i++){
            if (find(i) == find(u)){
                for (int j=0; j<N; j++){
                    if (find(j) == find(1)) connect(0, i, j);
                }
            }
        }
    }
    if (find(v) == find(1)){
        for (int i=0; i<N; i++){
            if (find(i) == find(u)){
                for (int j=0; j<N; j++){
                    if (find(j) == find(0)) connect(0, i, j);
                }
            }
        }
    }
    merge(u, v);
}

int hasEdge(int u, int v){
    if (am[u][v] == 2) return 1;
    connect(0, u, v);
    return 0;
}

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