Submission #572167

#	Time	Username	Problem	Language	Result	Execution time	Memory
572167		Leo121	Game (IOI14_game)	C++14	42 / 100	1088 ms	2780 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define for0(i, n) for(int i = 0; i < int(n); ++ i)
#define pb push_back

using namespace std;

typedef vector<int> vi;

const int maxn = 15e2;

vi graph[maxn];
bool visitado[maxn];
int N, U, V, aux;
vi::iterator it;

void dfs(int u){
    aux ++;
    visitado[u] = 1;
    if(aux == N){
        return;
    }
    for(auto v : graph[u]){
        if(!visitado[v] && !(min(u, v) == U && max(u, v) == V)){
            dfs(v);
            if(aux == N){
                return;
            }
        }
    }
}

void initialize(int n) {
    for0(i, n)
        for0(j, n)
            if(i != j)
                graph[i].pb(j);
    N = n;
}

int hasEdge(int u, int v) {
    U = min(u, v);
    V = max(u, v);
    if(u == v){
        return 0;
    }
    memset(visitado, 0, sizeof(visitado));
    aux = 0;
    dfs(0);
    if(aux == N){
        int num = 0;
        it = graph[u].begin();
        for(auto j : graph[u]){
            if(j == v){
                graph[u].erase(it + num);
                break;
            }
            num ++;
        }
        num = 0;
        it = graph[v].begin();
        for(auto j : graph[v]){
            if(j == u){
                graph[v].erase(it + num);
                break;
            }
            num ++;
        }
        return 0;
    }
    return 1;
}

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