Submission #315523

#	Time	Username	Problem	Language	Result	Execution time	Memory
315523		qpwoeirut	Game (IOI14_game)	C++17	100 / 100	532 ms	25336 KiB

game

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

const int MN = 1501;

using namespace std;

int N;
int rt[MN];
int sz[MN];

int root(int u) {
    if (rt[u] != u) {
        rt[u] = root(rt[u]);
    }
    return rt[u];
}

int ct[MN][MN];
void join(int u, int v) {
    int ru = root(u), rv = root(v);
    if (sz[ru] < sz[rv]) {
        swap(ru, rv);
    }
    for (int i=0; i<N; ++i) {
        //if (root(i) == i)
            ct[ru][i] += ct[rv][i];
            ct[i][ru] = ct[ru][i];
    }
    rt[rv] = ru;
    
    sz[ru] += sz[rv];
    //cerr << "ru,rv: " << ru << ' ' << root(rv) << endl;
}


void initialize(int n) {
    N = n;
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            ct[i][j] = 0;
        }
        rt[i] = i;
        sz[i] = 1;
    }
}

int hasEdge(int u, int v) {
    int ru = root(u), rv = root(v);
    ++ct[ru][rv];
    ct[rv][ru] = ct[ru][rv];
    
    int ret = 0;
    if (ct[ru][rv] == sz[ru] * sz[rv] && ct[rv][ru] == sz[ru] * sz[rv]) {
        join(u, v);
        //cerr << "ru,rv: " << root(u) << ' ' << root(v) << endl;
        //cerr << "joined u,v: " << u << ' ' << v << endl;
        ret = 1;
    }

    //cerr << "u,v: " << u << ' ' << v << ' ' << endl << "ru,rv,su,sv,ctu,ctv: " << ru << ' ' << rv << ' ' << sz[ru] << ' ' << sz[rv] << ' ' << ct[ru][rv] << ' ' << ct[rv][ru] << endl;
    //for (int i=0; i<N; ++i) { cerr << root(i) << ' '; } cerr << endl;
    //for (int i=0; i<N; ++i) {for (int j=0; j<N; ++j) cerr << ((root(i) == i && root(j) == j) ? ct[i][j] : 0) << ' '; cerr << endl;} cerr << endl;
    return ret;
}
/*
4
2 3
1 3
0 2
0 1
1 2
0 3


5
0 1
0 2
0 3
1 4
2 4
3 4
0 4
1 2
1 3
2 3

5
0 1
0 2
0 3
0 4
1 2
1 3
1 4
3 4
2 3
2 4

*/

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