Submission #1049499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049499		ArthuroWich	Game (IOI14_game)	C++17	100 / 100	208 ms	27484 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
int p[1505], s[1505], d[1505];
queue<int> q[1505];
int find(int x) {
    if (p[x] == x) {
        return x;
    }
    p[x] = find(p[x]);
    return p[x];
}
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) {
        return;
    }
    s[a]++;
    p[b] = a;
}
int h = -1, co = 0;
void initialize(int n) {
    h = -1;
    co = 0;
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
}
int hasEdge(int u, int v) {
    if (co == 0) {
        h = u;
        s[h] = 1;
        merge(h, v);
        co++;
        return 1;
    }
    if (find(u) == find(v)) {
        return 0;
    }
    if (find(u) == find(h)) {
        d[v]++;
        if (s[h]-d[v] == 0) {
            merge(h, v);
            while(!q[v].empty()) {
                d[q[v].front()]++;
                q[v].pop();
            }
            return 1;
        } else {
            q[v].push(u);
            return 0;
        }
    } else if (find(v) == find(h)) {
        d[u]++;
        if (s[h]-d[u] == 0) {
            merge(h, u);
            while(!q[u].empty()) {
                d[q[u].front()]++;
                q[u].pop();
            }
            return 1;
        } else {
            q[u].push(v);
            return 0;
        }
    } else {
        q[u].push(v);
        q[v].push(u);
        return 0;
    }
}

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