Submission #726952

#	Time	Username	Problem	Language	Result	Execution time	Memory
726952		vjudge1	Game (APIO22_game)	C++17	60 / 100	4062 ms	53144 KiB

game

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

int N, K;
int f[300000];
vector<int> adj[300000], radj[300000];

void init(int n, int k) {
        N = n, K = k;
        for (int i = 0; i < N; i++) f[i] = N;
}

priority_queue<pair<int, int>> pq[300000];

int add_teleporter(int u, int v) {
        adj[u].emplace_back(v);
        radj[v].emplace_back(u);
        pq[v].emplace(f[u], u);
        int F = v < K ? v : f[v];
        queue<int> q;
        q.emplace(v);
        while (q.size()) {
                int v = q.front();
                q.pop();
                while (pq[v].size()) {
                        auto [fu, u] = pq[v].top();
                        if (fu <= F) break;
                        pq[v].pop();
                        if (f[u] != fu) {
                                if (f[u] > F) q.emplace(u);
                                f[u] = min(f[u], F);
                                pq[v].emplace(f[u], u);
                                continue;
                        }
                        f[u] = F;
                        pq[v].emplace(f[u], u);
                        q.emplace(u);
                }
        }
        for (int i = 0; i < K; i++) {
                if (f[i] <= i) return 1;
        }
        return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 0 / 40