Submission #1313663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313663		timeflew	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	1599 ms	589824 KiB

bitaro

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

#define ll long long

const int mxN=1e5, mxM=2e5, B=300;

vector<int> adj[mxN];
vector<pair<int, int>> dist[mxN];
int n, m, q, deg[mxN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=0; i<m; i++) {
        int a, b;
        cin>>a>>b;
        --a, --b;
        adj[a].push_back(b);
        deg[b]++;
    }
    queue<int> qu;
    for(int i=0; i<n; i++)
        if(deg[i]==0) {
            qu.push(i);
            dist[i].push_back({0, i});
        }
    while(qu.size()) {
        int x=qu.front();
        qu.pop();
        for(int y : adj[x]) {
            if(--deg[y]==0) {
                qu.push(y);
                dist[y].push_back({0, y});
            }
            for(auto e : dist[x]) {
                dist[y].push_back({e.first+1, e.second});
            }
        }
        sort(dist[x].begin(), dist[x].end(), greater<pair<int, int>>());
        while(dist[x].size()>B)
            dist[x].pop_back();
    }
    while(q--) {
        int st;
        cin>>st;
        --st;
        int c;
        cin>>c;
        set<int> s;
        for(int i=0; i<c; i++) {
            int x;
            cin>>x;
            --x;
            s.insert(x);
        }
        if(c<B) {
            int ans=-1;
            for(auto [dis, x] : dist[st]) {
                if(s.find(x)==s.end()) {
                    ans=dis;
                    break;
                }
            }
            cout<<ans<<"\n";
        } else {
            vector<int> dis(n);
            for(int x : s)
                dis[x]=-1;
            for(int i=0; i<n; i++) {
                if(dis[i]==-1)
                    continue;
                for(int j : adj[i]) 
                    dis[j]=max(dis[i]+1, dis[j]);
            }
            cout<<dis[st]<<"\n";
        }
    }
    return 0;
}

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