Submission #392045

#	Time	Username	Problem	Language	Result	Execution time	Memory
392045		giorgikob	Game (IOI14_game)	C++14	100 / 100	483 ms	25228 KiB

game

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

#include "game.h"


const int N = 1505;

int par[N],sz[N],edges[N][N];

void initialize(int n) {
    for(int i = 0; i < n; i++){
        par[i] = i;
        sz[i] = 1;
        for(int j = 0; j < n; j++){
            edges[i][j] = 1;
        }
    }
}

int find_set(int x){
    if(par[x] == x) return x;
    return par[x] = find_set(par[x]);
}

inline void union_set(int x,int y,int n){
    if(sz[x] < sz[y]) swap(x,y);

    par[y] = x;
    sz[x] += y;
    vector<int>fix(n,0);
    for(int i = 0; i < n; i++){
        int j = find_set(i);
        if(fix[j]) continue;
        fix[j] = 1;
        edges[x][j] += edges[y][j];
        edges[j][x] += edges[y][j];
    }
}


int hasEdge(int u, int v) {

    u = find_set(u);
    v = find_set(v);

    if(u == v) return 0;

    if(edges[u][v] > 1){
        edges[u][v]--;
        edges[v][u]--;
        return 0;
    }

    assert(edges[u][v]);
    union_set(u,v,N);
    return 1;
}

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