제출 #1252407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252407		Muhammet	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1287 ms	416272 KiB

bitaro

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll long long
#define SZ(s) (int)s.size()
#define ff first
#define ss second

const int N = 1e5 + 5;

vector <int> v[N], vis, ds;

vector <pair <int, int>> V[N];

int k, ind[N], vis1[N];

void dfs(int x) {
    if(ds[x] != -(1e9 + 1)) return;
    ds[x] = (vis[x] ? 0 : -1e9);
    for(auto i : v[x]) {
        dfs(i);
        ds[x] = max(ds[x], ds[i] + 1);
    }
}

void f(int x) {
    if(vis[x]) return;
    vis[x] = true;
    priority_queue <pair <pair <int, int>, int>> q;
    for(auto i : v[x]) {
        f(i);
        q.push({V[i][0], i});
        ind[i] = 0;
    }
    while(SZ(V[x]) <= k and SZ(q)) {
        auto [d, Y] = (q.top()).ff;
        int y = (q.top()).ss;
        q.pop();
        if(!vis1[Y]) {
            V[x].push_back({d+1, Y});
            vis1[Y] = true;
        }
        ind[y]++;
        while(ind[y] < SZ(V[y]) and vis1[V[y][ind[y]].ss]) {
            ind[y]++;
        }
        if(ind[y] == SZ(V[y])) continue;
        q.push({V[y][ind[y]], y});
    }
    V[x].push_back({0, x});
    for(auto [i, j] : V[x]) {
        vis1[j] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    k = sqrt(n) + 5;

    for(int i = 1; i <= m; i++) {
        int u1, u2;
        cin >> u1 >> u2;
        v[u2].push_back(u1);
    }

    vis.assign(n+1, 0);
    for(int i = 1; i <= n; i++) {
        f(i);
    }

    vector <int> a;
    vis.assign(n+1, true);
    while(q--) {
        int t, y;
        cin >> t >> y;
        a.resize(y);
        for(int i = 0; i < y; i++) {
            cin >> a[i];
            vis[a[i]] = false;
        }
        if(y >= k) {
            ds.assign(n+1, -(1e9 + 1));
            dfs(t);
            cout << (ds[t] < 0 ? -1 : ds[t]) << '\n';
        }
        else {
            int ans = -1;
            for(auto [i, j] : V[t]) {
                if(vis[j]) {
                    ans = i;
                    break;
                }
            }
            cout << ans << '\n';
        }
        for(auto i : a) {
            vis[i] = true;
        }
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86