Submission #902260

#	Time	Username	Problem	Language	Result	Execution time	Memory
902260		Ghulam_Junaid	Game (IOI14_game)	C++17	0 / 100	1 ms	2536 KiB

game

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

const int MXN = 1505;
int n, par[MXN], seen[MXN][MXN];
vector<int> S[MXN];

int root(int v){
    return ((par[v] == -1) ? (v) : (par[v] = root(par[v])));
}

void merge(int u, int v){
    if ((u = root(u)) == (v = root(v)))
        return;

    if (S[u].size() > S[v].size())
        swap(u, v);

    par[u] = v;
    for (int x : S[u])
        S[v].push_back(x);
    S[u].clear();
}

void initialize(int N){
    n = N;
    for (int i=0; i<n; i++){
        S[i].push_back(i);
        par[i] = -1;
    }
}
int hasEdge(int u, int v){
    seen[u][v] = 1;

    u = root(u), v = root(v);
    if (u == v) return 0;

    int cnt = 0;
    for (int x : S[u])
        for (int y : S[v])
            cnt += seen[x][y];

    int total = S[u].size();
    int sz = S[v].size();
    total *= sz;
    
    if (cnt == total ){
        merge(u, v);
        return 1;
    }

    return 0;
}

// int main(){
//     int n;
//     cin >> n;

//     initialize(n);
//     for (int i=0; i<(n * (n - 1)) / 2; i++){
//         int u, v;
//         cin >> u >> v;

//         cout << hasEdge(u, v) << endl;
//     }
// }

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