Submission #103556

#	Time	Username	Problem	Language	Result	Execution time	Memory
103556		SecretAgent007	Game (IOI14_game)	C++17	100 / 100	736 ms	24460 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

vector< int > U;

int getParents(int a){
    if(U[a] == a) return a;
    return U[a] = getParents(U[a]);
}

void Union(int a, int b){
    U[getParents(a)] = getParents(b);
}

int N;

vector< int > S;
vector< vector< int> > badEdge;

void initialize(int n){
    N = n;
    U.resize(n);
    badEdge.resize(n,vector<int>(n,0));
    for(int i = 0; i < n; i++) U[i] = i;
    S.resize(n,1);
}
int hasEdge(int u, int v) {

    int a = getParents(u);
    int b = getParents(v);

    if(S[a]*S[b]-1 == badEdge[a][b]){

        S[b] += S[a];
        for(int i = 0; i < N; i++){
            badEdge[b][i] += badEdge[a][i];
            badEdge[i][b] += badEdge[i][a];
        }
        Union(a,b);

        return 1;
    }

    badEdge[a][b]++, badEdge[b][a]++;
    return 0;
}
/*
signed main(){
    int n;
    cin >> n;
    initialize(n);
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            cout << i << ' ' << j << ' ' << hasEdge(i,j) << endl;
        }
    }
}
*/

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