Submission #1062816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062816		YassineBenYounes	Game (IOI14_game)	C++17	42 / 100	1100 ms	3668 KiB

game

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

#define vi vector<int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define vii vector<pii>
#define ff first
#define ss second
const int mx = 1505;
int n;
int par[mx], sz[mx];
vii queries;
bool adj[mx][mx];
bitset<mx> compo[mx];
vi nodes[mx];
int find_par(int x){
    if(x == par[x])return x;
    return par[x] = find_par(par[x]);
}

void initialize(int N){
    n = N;
    for(int i = 0; i < n;i++){
        par[i] = i;
        sz[i] = 1;
        nodes[i].pb(i);
        compo[i][i] = 1;
    }
}
int hasEdge(int u, int v){
    int a = u, b = v;
    u = find_par(u);
    v = find_par(v);
    if(sz[u] > sz[v])swap(u, v);
    if(u == v){
        adj[b][a] = adj[a][b] = 1;
        return 0;
    }
    int tot = sz[u] * sz[v] - 1;
    int cnt = 0;
    for(int x : nodes[u]){
        for(int y : nodes[v]){
            cnt += adj[x][y];
        }
    }
    adj[b][a] = adj[a][b] = 1;
    if(tot == cnt){
        for(int x : nodes[u]){
            nodes[v].pb(x);
        }
        sz[v] += sz[u];
        par[u] = v;
        return 1;
    }
    return 0;
}

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