Submission #780806

#	Time	Username	Problem	Language	Result	Execution time	Memory
780806		fatemetmhr	Game (IOI14_game)	C++17	100 / 100	314 ms	25164 KiB

game

//  ~ Be Name Khoda ~  //

#include "game.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1502;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n, par[maxn5], cnt[maxn5][maxn5], sz[maxn5];

int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}

void initialize(int nn) {
    n = nn;
    memset(par, -1, sizeof par);
    fill(sz, sz + maxn5, 1);
}

int hasEdge(int u, int v){
    u = get_par(u);
    v = get_par(v);
    //cout << u << ' ' << v << ' ' << sz[u] << ' ' << sz[v] << ' ' << cnt[u][v] << endl;
    if(cnt[u][v] + 1 == sz[u] * sz[v]){
        par[u] = v;
        sz[v] += sz[u];
        for(int i = 0; i < n; i++) if(i != u && i != v && par[i] == -1)
            cnt[i][v] = cnt[v][i] = cnt[i][u] + cnt[i][v];
        return 1;
    }
    cnt[u][v]++;
    cnt[v][u]++;
    return 0;
}

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