Submission #423193

#	Time	Username	Problem	Language	Result	Execution time	Memory
423193		snasibov05	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	4 ms	844 KiB

bitaro

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
#define oo 1000000000

const int b = 320;

vector<vector<int>> ed;
vector<vector<pii>> mx;
vector<bool> visited;
vector<int> dist;
vector<int> dp;

void dfs(int v){
    visited[v] = true;

    for (auto to : ed[v]){
        if (!visited[to]) dfs(to);
        for (auto x : mx[v]){
            dist[x.s] = x.f;
        }
        for (auto x : mx[to]) {
            dist[x.s] = max(dist[x.s], x.f + 1);
        }
        for (auto& x : mx[v]){
            x.f = max(x.f, dist[x.s]); dist[x.s] = 0;
        }
        for (auto x : mx[to]){
            if (dist[x.s] == 0) continue;
            mx[v].pb({x.f+1, x.s}); dist[x.s] = 0;
        }

        sort(mx[v].rbegin(), mx[v].rend());
        while (mx[v].size() > b) mx[v].pop_back();
    }
    
    if (mx[v].size() < b) mx[v].pb({0, v});
}

void calc(int v, vector<bool>& busy){
    visited[v] = true;
    if (busy[v]) dp[v] = -1;
    for (auto to : ed[v]){
        if (!visited[to]) calc(to, busy);
        if (busy[to]) continue;
        dp[v] = max(dp[v], dp[to] + 1);
    }
}

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

    int n, m, q; cin >> n >> m >> q;
    ed.resize(n+1);
    mx.resize(n+1);
    visited.resize(n+1);
    dist.resize(n+1);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        ed[v].pb(u);
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) dfs(i);
    }

    vector<bool> busy(n+1);

    for (int i = 0; i < q; ++i) {
        int t, y; cin >> t >> y;
        vector<int> cur(y);
        for (int j = 0; j < y; ++j) {
             cin >> cur[j];
             busy[cur[j]] = true;
        }

        if (y < b){
            int ans = -1;
            for (auto x : mx[t]){
                //cout << x.f << " " << x.s << "\n";
                if (!busy[x.s]) {
                    ans = x.f; break;
                }
            }
            cout << ans << "\n";
        } else{
            visited.assign(n+1, false);
            dp.assign(n+1, 0);
            for (int j = 1; j <= n; ++j) {
                if (!visited[j]) calc(j, busy);
            }
            cout << dp[t] << "\n";
        }

        for (auto x : cur) busy[x] = false;
    }

    return 0;
}

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