Submission #656359

#	Time	Username	Problem	Language	Result	Execution time	Memory
656359		Ronin13	Game (IOI14_game)	C++14	100 / 100	370 ms	25164 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define s second
using namespace std;

int n;
vector <int> sz(1501);
vector <int> p(1501);
int cnt[1501][1501];

void make_set(int v){
    sz[v] = 1;
    p[v] = v;
    for(int i = 1; i <= n; i++){
        cnt[v][i] = 1;
    }
}

int find_set(int v){
    return p[v] == v ? v : p[v] = find_set(p[v]);
}

int union_sets(int a,int b){
    a = find_set(a);
    b = find_set(b);
    if(a == b) return 0;
    cnt[a][b]--;
    cnt[b][a]--;
    if(!cnt[a][b]){
        if(sz[a] < sz[b]) swap(a, b);
        for(int i = 1; i <= n; i++){
            cnt[i][a] += cnt[i][b];
            cnt[a][i] += cnt[b][i];
        }
        p[b] = a;
        return 1;
    }
    return 0;
}

void initialize(int N) {
    n = N;
    for(int i = 1; i <= n; i++) make_set(i);
}

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

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