Submission #805208

#	Time	Username	Problem	Language	Result	Execution time	Memory
805208		HaroldVemeno	Game (IOI14_game)	C++17	100 / 100	362 ms	34004 KiB

game

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

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int n;
int nam[1500][1500];
int vis[1500][1500];
int uf[1500];
int us[1500];

int root(int x) {
    if(uf[x] == uf[uf[x]]) return uf[x];
    uf[x] = root(uf[x]);
    return uf[x];
}

void initialize(int N) {
    n = N;
    for(int i = 0; i < n; ++i) uf[i] = i;
    for(int i = 0; i < n; ++i) us[i] = 1;
}

int hasEdge(int u, int v) {
    int ru = root(u);
    int rv = root(v);
    int res = 0;
    if(vis[u][v]) {
        res = vis[u][v]-1;
    } else if(ru == rv) {
        res = 1;
    } else if(nam[ru][rv]+1 == us[ru]*us[rv]) {
        res = 1;
        uf[ru] = rv;
        us[rv] += us[ru];
        for(int i = 0; i < n; ++i) {
            nam[rv][i] += nam[ru][i];
            nam[i][rv] = nam[rv][i];
        }
    } else {
        res = 0;
        nam[ru][rv] += 1;
        nam[rv][ru] += 1;
    }
    vis[u][v] = res+1;
    return res;
}

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