Submission #103770

#	Time	Username	Problem	Language	Result	Execution time	Memory
103770		Osama_Alkhodairy	Game (IOI14_game)	C++17	100 / 100	806 ms	27812 KiB

game

#include <bits/stdc++.h>
#include "game.h"
//#include "grader.h"
//#include "grader.cpp"
using namespace std;

const int N = 1501;

int n, dsu[N], ok[N][N], sz[N];
vector <vector <int> > cnt;

int find(int x){
    if(dsu[x] == x) return x;
    return dsu[x] = find(dsu[x]);
}
void initialize(int nn){
    n = nn;
    cnt.assign(n, vector <int>(n, 0));
    for(int i = 0 ; i < n ; i++)
        dsu[i] = i, sz[i] = 1;
    for(int i = 0 ; i < n ; i++){
        for(int j = i + 1 ; j < n ; j++){
            ok[i][j] = ok[j][i] = 1;
        }
    }
}
void merge(int x, int y){
    sz[x] += sz[y];
    dsu[y] = x;
    for(int i = 0 ; i < n ; i++)
        cnt[x][i] += cnt[y][i];
    for(int i = 0 ; i < n ; i++){
        if(find(i) == i && i != x){
            ok[i][x] = ok[x][i] = sz[x] * sz[i];
        }
    }
    for(int i = 0 ; i < n ; i++){
        int r = find(i);
        if(r == x) continue;
        ok[x][r] -= cnt[x][i];
        ok[r][x] -= cnt[x][i];
    }
}
int hasEdge(int u, int v){
    int x = find(u);
    int y = find(v);
    if(x == y) return 1;
    ok[x][y]--;
    ok[y][x]--;
    cnt[x][y]++;
    cnt[y][x]++;
    if(ok[x][y] == 0){
        merge(x, y);
        return 1;
    }
    return 0;
}

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