Submission #1041101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041101		vanea	Game (IOI14_game)	C++14	0 / 100	1 ms	2556 KiB

game

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

const int mxN = 2e3+10;

int p[mxN], n, s[mxN][mxN];
set<int> comp;

int get(int x) {
    return (p[x] < 0 ? x : p[x] = get(p[x]));
}

void uni(int x, int y) {
    x = get(x); y = get(y);
    if(x == y) return ;
    if(p[x] > p[y]) swap(x, y);
    comp.erase(y);
    for(auto it : comp) {
        if(it == x) continue;
        s[x][it] = s[it][x] = s[x][it] + s[y][it];
    }
    p[x] += p[y];
    p[y] = x;
}

int hasEdge(int a, int b) {
    if(s[get(a)][get(b)] == 1) {
        uni(a, b);
        return 1;
    }
    --s[get(a)][get(b)];
    return 0;
}

void initialize(int N) {
    n = N;
    for(int i = 0; i < n; i++) p[i] = -1;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            s[get(i)][get(j)] = s[get(j)][get(i)] = 1;
        }
        comp.insert(i);
    }
}

/*
int main()
{
    initialize(4);
    cout << hasEdge(0, 1) << hasEdge(3, 0) << hasEdge(1, 2) << hasEdge(0, 2);
    cout << hasEdge(3, 1) << hasEdge(2, 3);
}*/

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