Submission #779235

#	Time	Username	Problem	Language	Result	Execution time	Memory
779235		fatemetmhr	Game (IOI14_game)	C++17	42 / 100	1087 ms	4800 KiB

game

//  ~ Be Name Khoda ~  //

#include "game.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n, q[maxn5], par[maxn5], per[maxn5];
bool av[maxn5][maxn5];
set <pair<int, int>> have, keep;

bool bfs(){
    //cout << "in bfs " << endl;
    shuffle(per, per + n, rng);
    int l = 0, r = 1;
    q[0] = per[0];
    keep = have;
    have.clear();
    memset(par, -1, sizeof par);
    par[per[0]] = 0;
    while(l < r){
        int v = q[l++];
        for(int i = 0; i < n; i++) if(par[per[i]] == -1 && av[v][per[i]]){
            par[per[i]] = v;
            have.insert({v, per[i]});
            //cout << "ok " << v << ' ' << i << endl;
            q[r++] = per[i];
        }
    }
    return r == n;
}


void initialize(int nn) {
    n = nn;
    memset(av, true, sizeof av);
    for(int i = 0; i < n; i++)
        per[i] = i;
    bfs();
}

int hasEdge(int u, int v){
    //cout << "ok in " << u << ' ' << v << endl;
    if(have.find(mp(u, v)) == have.end() && have.find(mp(v, u)) == have.end()){
        av[u][v] = av[v][u] = false;
        return 0;
    }
    av[u][v] = av[v][u] = false;
    bool ok = bfs();
    //cout << "hey " << ok << endl;
    if(ok)
        return 0;
    av[u][v] = av[v][u] = true;
    have = keep;
    return 1;
}

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