Submission #136164

#	Time	Username	Problem	Language	Result	Execution time	Memory
136164		zoooma13	Game (IOI14_game)	C++14	42 / 100	1024 ms	4472 KiB

game

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

#define MAX_N 1503
#define all(v) (v).begin() ,(v).end()

int n;
vector <int> adj[MAX_N];

vector <pair<int ,int>> tree;
vector <bool> bld_vis;
void bld_tree(int u){
    bld_vis[u] = 1;
    for(int&v : adj[u]) if(!bld_vis[v]){
        tree.push_back({u ,v});
        bld_tree(v);
    }
}
void get_tree(){
    fill(bld_vis.begin() ,bld_vis.end() ,0);
    tree.clear();
    bld_tree(rand()%n);
}

void initialize(int N) {
    n = N;
    bld_vis.resize(n);
    for(int u=0; u<n; u++){
        for(int v=u+1; v<n; v++){
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        random_shuffle(all(adj[u]));
    }
    get_tree();
}

int conn = 0;
bool vis[MAX_N];
void dfs(int u){
    vis[u] = 1 ,conn++;
    for(auto&v : adj[u]) if(!vis[v])
        dfs(v);
}

int hasEdge(int u, int v) {
    adj[u].erase(find(all(adj[u]) ,v));
    adj[v].erase(find(all(adj[v]) ,u));

    if(find(all(tree) ,make_pair(u ,v)) != tree.end()
    || find(all(tree) ,make_pair(v ,u)) != tree.end()){
        memset(vis ,0 ,sizeof vis) ,conn = 0 ,dfs(u);
        if(conn == n){
            get_tree();
            return 0;
        }else{
            adj[u].push_back(v); random_shuffle(all(adj[u]));
            adj[v].push_back(u); random_shuffle(all(adj[v]));
            return 1;
        }
    }
    return 0;
}

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