Submission #494034

#	Time	Username	Problem	Language	Result	Execution time	Memory
494034		TeaTime	Game (IOI14_game)	C++17	100 / 100	455 ms	39876 KiB

game

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <tuple>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef long double ld;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 2000;
ll dsu[SZ], add[SZ][SZ], nn;
int par(int v) {
    if (dsu[v] == v) return dsu[v];
    return dsu[v] = par(dsu[v]);
}
void uni(int v, int u) {
    v = par(v);
    u = par(u);
    if (u != v) {
        dsu[u] = v;
        for (int i = 0; i < nn; i++) {
            add[v][i] += add[u][i];
            add[i][v] += add[u][i];
        }
    }
}


void initialize(int n) {
    for (int i = 0; i < n; i++) dsu[i] = i;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) add[i][j] = 1;
    nn = n;
}

int hasEdge(int u, int v) {
    if (u > v) swap(u, v);
    int n = nn;
    u = par(u);
    v = par(v);
    int cnt = add[u][v];

    if (cnt == 1) {
        uni(u, v);
        return 1;
    }

    add[u][v]--;
    add[v][u]--;

    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:44:9: warning: unused variable 'n' [-Wunused-variable]
   44 |     int n = nn;
      |         ^

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