Submission #168358

#	Time	Username	Problem	Language	Result	Execution time	Memory
168358		mat_v	Game (IOI14_game)	C++14	100 / 100	530 ms	23384 KiB

game

#include <bits/stdc++.h>
#include "game.h"
//#define maxn
using namespace std;
int dsu[2505];
int vel[2505];
int ima[2505][2505];
vector<int> graf[2505];
bool bio[2505];
int bet[2505][2505];
int n;
void init(){
    for(int i=1; i<=n; i++){
        dsu[i] = i;
        vel[i] = 1;
    }
}
int findpar(int x){
    if(x == dsu[x])return x;
    return dsu[x] = findpar(dsu[x]);
}
int unite(int x, int y){
    int a = findpar(x);
    int b = findpar(y);
    if(a == b){
        return 0;
    }
    int uk = vel[a] * vel[b];
    bet[a][b]++;
    bet[b][a]++;
    if(uk == bet[a][b]){
        vel[a] += vel[b];
        dsu[b] = a;
        for(int i=1; i<=n; i++){
            bet[a][i] += bet[b][i];
            bet[i][a] += bet[i][b];
        }
        return 1;
    }
    return 0;
}
void dfs(int x){
    bio[x] = 1;
    for(int i=1; i<=n; i++){
        if(!bio[i]){
            if(ima[x][i] != 2)dfs(i);
        }
    }
}
void probaj(int src){
    for(int i=1; i<=n; i++)bio[i] = 0;
    dfs(src);
}

void initialize(int m) {
    n = m;
    init();
}

int hasEdge(int u, int v) {
    u++;
    v++;
    return unite(u,v);
}

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