Submission #750623

#	Time	Username	Problem	Language	Result	Execution time	Memory
750623		Abrar_Al_Samit	Game (IOI14_game)	C++17	0 / 100	1 ms	340 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int nax = 1500;
int g[nax][nax];
int n;

int sz[nax], qr[nax], par[nax];


void initialize(int N) {
    n = N;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) if(i!=j) {
            g[i][j] = 2;
        }
    }

    for(int i=0; i<n; ++i) {
        sz[i] = 1, par[i] = i, qr[i] = 0;
    }
}

int find(int v) {
    return par[v] = (v==par[v]) ? v : find(par[v]);
}
void unite(int u, int v) {
    u = find(u), v = find(v);

    if(sz[u] < sz[v]) swap(u, v);

    qr[u] = (qr[u] + qr[v] - 2 * (sz[u] * sz[v] - 1));

    sz[u] += sz[v];
    par[v] = u;
}
bool must(int v) {
    v = find(v);
    if(qr[v]==sz[v] * (n-sz[v]) - 1) return 1;
    return 0;
}
int hasEdge(int u, int v) {
    if(u==v) return 0;

    if(g[u][v]!=2) return g[u][v];
    if(find(u)==find(v)) return 0;

    for(int x : {u, v}) {
        if(must(x)) {
            unite(u, v);
            return g[u][v] = g[v][u] = 1;
        }
    }

    qr[find(u)]++;
    qr[find(v)]++;

    return g[u][v] = g[v][u] = 0;
}

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