이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |