Submission #595093

#	Time	Username	Problem	Language	Result	Execution time	Memory
595093		shrimb	Game (IOI14_game)	C++17	100 / 100	997 ms	17084 KiB

game

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

bitset<1500> adj[1500], st[1500], badst;
int n;
// adj[i][j] = 1 if there is an edge from i to j which still exists
// st[i][j] = 1 if the edge from i to j is an edge in the st
// badst[i] = 1 if the node i is connected to v through the edges of the st after edge u v is deleted
vector<int> madj[1500];

void initialize(int N) {
    n = N;
    for (int i = 0 ; i < n ; i++) {
        if (i + 1 < n) {
            st[i][i + 1] = 1;
            st[i + 1][i] = 1;
            madj[i].push_back(i + 1);
            madj[i + 1].push_back(i);
        }
        adj[i] = 0;
        for (int j = 0 ; j < n ; j++) {
            adj[i][j] = i != j;
        }
    }
}

int badu;

void dfs (int cur) {
    // cerr << cur << endl;
    badst[cur] = 1;
    for (int j : madj[cur]) {
        if (j != badu and badst[j] == 0) dfs(j);
    }
}

int hasEdge(int u, int v) {
    if (!st[u][v]) {
        adj[u][v] = 0;
        adj[v][u] = 0;
        return 0;
    }

    badst = 0;
    badu = u;
    dfs(v);
    adj[u][v] = adj[v][u] = 0;
    for (int i = 0 ; i < n ; i++) {
        if (!badst[i]) {
            auto j = adj[i] & badst;
            int k = j._Find_first();
            if (k < n) {
                st[u][v] = st[v][u] = 0;
                st[i][k] = st[k][i] = 1;
                madj[u].erase(find(madj[u].begin(), madj[u].end(), v));
                madj[v].erase(find(madj[v].begin(), madj[v].end(), u));
                madj[i].push_back(k);
                madj[k].push_back(i);
                // cerr << i << " " << k << endl;
                return 0;
            }
        }
    }
    adj[u][v] = adj[v][u] = 1;
    return 1;

}

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