Submission #489155

#	Time	Username	Problem	Language	Result	Execution time	Memory
489155		SlavicG	Game (IOI14_game)	C++17	100 / 100	376 ms	17748 KiB

game

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 1600;
bool asked[N][N];
bool know[N][N];
int par[N], s[N];
int cnt[N][N];
int n;
int get(int a){
    return (a == par[a] ? a : par[a] = get(par[a]));
}
void uni(int a, int b){
    a = get(a), b = get(b);
    if(a == b)return;
    if(s[a] > s[b])swap(a, b);

    for(int i = 0;i < n; ++i){
        if(i == a || i == b)continue;
        cnt[i][b] += cnt[i][a];
        cnt[b][i] += cnt[a][i];
    }
    par[a] = b;
    s[b] += s[a];
}

void initialize(int N){
    n = N;
    for(int i = 0;i < n; ++i){
        s[i] = 1;
        par[i] = i;
    }

    for(int i = 0;i < n; ++i){
        for(int j = 0;j < n; ++j){
            cnt[i][j] = 1;
        }
    }
}

int hasEdge(int u, int v){
    u = get(u), v = get(v);

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

    uni(u, v);
    return 1;
}

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