Submission #586299

#	Time	Username	Problem	Language	Result	Execution time	Memory
586299		MadokaMagicaFan	Game (IOI14_game)	C++14	100 / 100	350 ms	25164 KiB

game

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

int n;
const int N = 1500;

int p[N];
int s[N];

int edg[N][N];

int
par(int x)
{
    return p[x] = (x == p[x]) ? x : par(p[x]);
}

void
uni(int a, int b)
{
    a = par(a);
    b = par(b);

    if (a == b) return;
    if (s[a] > s[b]) swap(a,b);

    for (int i = 0; i < n; ++i) {
        if (i == b || i == a) continue;
        edg[b][i] += edg[a][i];
        edg[i][b] += edg[i][a];
    }

    p[a] = b;
    s[b] += s[a];
    return;
}

int
hasEdge(int u, int v)
{
    if (u == v) return 0;
    u = par(u); v = par(v);
    if (u == v) return 1;

    ++edg[u][v];
    ++edg[v][u];
    if (edg[u][v] == s[u] * s[v]) {
        uni(u,v);
        return 1;
    }


    return 0;
}

void
initialize(int _n)
{
    n = _n;

    for (int i = 0; i < n; ++i) {
        p[i] = i;
        s[i] = 1;
    }
    return;
}


#ifdef ONPC
void
solve()
{
    int _n;
    scanf("%d", &_n);

    initialize(_n);

    int a, b;
    do {
        printf("? ");
        fflush(stdout);
        scanf("%d %d", &a, &b);
        printf("! %d\n", hasEdge(a,b));
    } while(a^b);
}

int32_t
main(int argc, char **argv)
{
    /* if (argc >= 2) { */
    /*     freopen(argv[1], "r", stdin); */
    /* } else */
    /*     ios_base::sync_with_stdio(0);cin.tie(0); */
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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