제출 #726950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726950		vjudge1	게임 (APIO22_game)	C++17	30 / 100	1781 ms	262144 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) {
                                f[u] = min(f[u], F);
                                pq[v].emplace(f[u], u);
                        }
                        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: 0 / 30
• Subtask 5: 0 / 40