Submission #813594

#	Time	Username	Problem	Language	Result	Execution time	Memory
813594		Liudas	Game (IOI14_game)	C++17	42 / 100	1087 ms	12732 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
static const int buf_size = 4096;
vector<set<int>> tree;
int s;
void initialize(int N){
    tree.assign(N, {});
    s = N;
    for(int i = 0; i < N; i ++){
        for(int j = i + 1; j < N; j ++){
            tree[i].insert(j);
            tree[j].insert(i);
        }
    }
}
void dfs(int head, vector<set<int>> &tree, vector<bool> &vis, int &c){
    c ++;
    vis[head] = true;
    for(int i : tree[head]){
        if(!vis[i]){
            dfs(i, tree, vis, c);
        }
    }
}
int hasEdge(int u, int v){
    tree[u].erase(v);
    tree[v].erase(u);
    vector<bool> vis(s, false);
    int c = 0;
    dfs(0, tree, vis, c);
    if(c == s){
        return 0;
    }
    else{
        tree[u].insert(v);
        tree[v].insert(u);
        return 1;
    }
}

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