Submission #403254

#	Time	Username	Problem	Language	Result	Execution time	Memory
403254		Pichon5	Game (IOI14_game)	C++17	100 / 100	458 ms	25280 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define F first
#define S second
using namespace std;
const int tam=1505;
int P[tam];
int M[tam][tam];
int sz[tam];
int N;
int _find(int x){
    if(P[x]==x)return x;
    return P[x]=_find(P[x]);
}
void _union(int x, int y){
    if(sz[x]<sz[y])swap(x,y);//quiero añadir todo a x
    P[y]=x;
    sz[x]+=y;
    vector<bool>vis(N+1,false);
    for(int i=0;i<N;i++){
        int j=_find(i);
        if(vis[j])continue;
        vis[j]=1;
        M[x][j]+=M[y][j];
        M[j][x]+=M[y][j];
    }


}
void initialize(int n) {
    N=n;
    for(int i=0;i<=n;i++){
        P[i]=i;
    }
    for(int i=0;i<n;i++){
        sz[i]=1;
        for(int l=0;l<n;l++){
            M[i][l]=1;
        }
    }
}

int hasEdge(int u, int v) {
    u=_find(u);
    v=_find(v);
    if(v==u)return 0;
    if(M[u][v]>1){
        M[u][v]--;
        M[v][u]--;
        return 0;
    }
    _union(u,v);
    return 1;
}

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