Submission #959675

#	Time	Username	Problem	Language	Result	Execution time	Memory
959675		vjudge1	Game (IOI14_game)	C++17	42 / 100	1022 ms	13076 KiB

game

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

const int N = 1500;

int n, cnt, idx, sum, a[N];
unordered_set<int> vis, adj[N];

void dfs(int x) {
    vis.insert(x);

    sum++;
    if (sum >= idx) return;

    for (int y : adj[x]) {
        if (vis.find(y) != vis.end()) continue;

        dfs(y);
        if (sum >= idx) return;
    }
}

void initialize(int NN) {
    n = NN;
    cnt = 0;
    idx = 1;

    a[1] = 0;
    for (int i = 2; i <= n; i++) {
        a[i] = (n-i+1) * (i-1);
    }

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            adj[i].insert(j);
            adj[j].insert(i);
        }
    }
}

int hasEdge(int u, int v) {
    cnt++;
    while (idx+1 <= n && a[idx+1] <= cnt && a[idx+1] > a[idx]) idx++;

    adj[u].erase(v);
    adj[v].erase(u);

    vis.clear();
    sum = 0;
    dfs(u);
    if (sum < idx) {
        adj[u].insert(v);
        adj[v].insert(u);
        return 1;
    }

    vis.clear();
    sum = 0;
    dfs(v);
    if (sum < idx) {
        adj[u].insert(v);
        adj[v].insert(u);
        return 1;
    }

    return 0;
}

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