제출 #1148131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148131		josephtenorio	게임 (IOI14_game)	C++20	100 / 100	219 ms	15960 KiB

game

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

queue<int> lid;
vector<vector<int>> adj;
vector<int> dsu;

int padre(int n) {
    if (dsu[n] == n) return n;
    return dsu[n] = padre(dsu[n]);
}

bool hasEdge(int a, int b) {
    int la = padre(a);
    int lb = padre(b);
    if (adj[la][lb] == 1) {
        dsu[la] = lb;
        int l = lid.size();
        for (int t1 = 0; t1 < l; t1 ++) {
            int li = lid.front();
            lid.pop();
            if (li == la) continue ;
            if (li == lb) {
                lid.push(li);
                continue;
            }
            adj[lb][li] += adj[la][li];
            adj[li][lb] += adj[li][la];
            lid.push(li);
        }
        //for (auto a: adj) {
        //    for (auto b:a) {
        //        cout << b << " ";
        //    }
        //    cout << endl;
        //}
        //cout << endl;
        return true;
    } else {
        adj[la][lb] --;
        adj[lb][la] --;
        //for (auto a: adj) {
        //    for (auto b:a) {
        //        cout << b << " ";
        //    }
        //    cout << endl;
        //}
        //cout << endl;
        return false;
    }
}

void initialize(int n) {
    dsu.resize(n);
    adj.resize(n, vector<int>(n, 1));
    for (int t1 = 0; t1 < n; t1 ++) {
        adj[t1][t1] = 0;
        lid.push(t1);
        dsu[t1] = t1;
    }
    //for (auto a: adj) {
    //    for (auto b:a) {
    //        cout << b << " ";
    //    }
    //    cout << endl;
    //}
    //cout << endl;
    return ;
}

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