Submission #504963

#	Time	Username	Problem	Language	Result	Execution time	Memory
504963		amukkalir	Game (IOI14_game)	C++17	42 / 100	1063 ms	9136 KiB

game

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

const int nax = 1500; 
int g[nax][nax], f[nax][nax]; 
int alr[nax][nax]; 
int n; 
set<int> rem[nax+5]; 

void initialize(int N) {
    n = N; 
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) g[i][j] = (i!=j); 
}

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]; 
    vector<bool> vis(n, false); //if the algo is correct, u and v should not have been connected indirectly

    function <void(int, int)> rec = [&] (int node, int x) {
        vis[node] = true; 
        a[x].push_back(node);
        for(int i=0; i<n; i++) {
            if(vis[i] == false && f[node][i] == 1) {
                rec(i, x); 
            }
        }
    };

    rec(u, 0); rec(v, 1); 

    for(int x : a[0]) {
        for(int y : a[1]) {
            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)) {
        f[u][v] = f[v][u] = 1; 
    } else {
        g[u][v] = g[v][u] = 0; 
    }
    return g[u][v]; 
}

/*

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: 0 / 58