Submission #504991

#	Time	Username	Problem	Language	Result	Execution time	Memory
504991		amukkalir	Game (IOI14_game)	C++17	100 / 100	686 ms	19488 KiB

game

#include "game.h"
#include <bits/stdc++.h> 
using namespace std; 
 
const int nax = 1500; 
int alr[nax][nax]; 
int p[nax]; 
map<int, vector<int>> mem; 
int n; 
 
int par(int a) {
    return p[a] == a ? a : p[a] = par(p[a]); 
}
 
void join (int a, int b) {
    for(auto x : mem[par(a)]) { //since a and b should not have any overlapping member isoke vector aj
        mem[par(b)].push_back(x); 
    }

    mem[par(a)].clear(); 

    p[par(a)] = par(b); 
}
 
void initialize(int N) {
    n = N; 
    for(int i=0; i<n; i++) p[i] = i, mem[i] = {i}; 
}
 
void udhin(int u, int v) {
    alr[u][v] = alr[v][u] = true; 
}
 
bool ud(int u, int v) {
    return alr[u][v]; 
}
 
bool ok (int u, int v) {
    vector<int> a[2]; 
    a[0] = mem[par(u)], a[1] = mem[par(v)]; 
 
    for(int x : a[0]) {
        for(int y : a[1]) {
            //cerr << x << " " << y << endl; 
            if(!ud(x, y)) return false; //kalau ada yg belum ditanya, ga boleh bikin edge
        }
    }
 
    return true; 
}
 
int hasEdge(int u, int v) {
    udhin(u, v); 

    if(ok(u, v)) {
        join(u, v); 
        return 1; 
    } else {
        return 0; 
    }
}
 
/*
 
ga boleh guess node itu connected sebelum r
gak boleh tau 2 node itu connected sebelum ditanyain 
dgn kata lain, ga boleh ada 2 node yang indirectly connected 
(unless 2 node itu udah ditanya)
 
ga bolleh guess node itu disconnected sblm r
ga boleh ada 1 pun node yang ga connect ke edge manapun, kecuali 
node yang ditanya terakhir 
 
*/

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