Submission #1252371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252371		Muhammet	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2098 ms	147320 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];

map <int, bool> mp;

int k, ind[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;
    set <pair <pair <int, int>, int>> s;
    mp.clear();
    for(auto i : v[x]) {
        f(i);
        s.insert({V[i][0], i});
        ind[i] = 0;
    }
    while(SZ(V[x]) < k and SZ(s)) {
        auto [d, Y] = (*s.rbegin()).ff;
        int y = (*s.rbegin()).ss;
        s.erase(--s.end());
        if(mp.find(Y) == mp.end()) {
            V[x].push_back({d+1, Y});
            mp[Y] = true;
        }
        ind[y]++;
        if(ind[y] == SZ(V[y])) continue;
        s.insert({V[y][ind[y]], y});
    }
    V[x].push_back({0, x});
}

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;
    while(q--) {
        int t, y;
        cin >> t >> y;
        a.resize(y);
        for(int i = 0; i < y; i++) {
            cin >> a[i];
        }
        if(y > k) {
            vis.assign(n+1, true);
            for(auto i : a) {
                vis[i] = false;
            }
            ds.assign(n+1, -(1e9 + 1));
            dfs(t);
            cout << (ds[t] < 0 ? -1 : ds[t]) << '\n';
            continue;
        }
        mp.clear();
        for(auto i : a) {
            mp[i] = true;
        }
        int ans = -1;
        for(auto [i, j] : V[t]) {
            if(mp.find(j) == mp.end()) {
                ans = i;
                break;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

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