Submission #1313726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313726		timeflew	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2093 ms	20020 KiB

bitaro

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

#define ll long long

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

vector<int> adj[mxN];
set<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].insert({i ,i});
        }
	vector<int> d(n, -1);
    while(qu.size()) {
        int x=qu.front();
        qu.pop();
        for(int y : adj[x]) {
            if(--deg[y]==0) {
                qu.push(y);
                dist[y].insert({y, 0});
            }
            for(auto e : dist[x]) {
				auto it=dist[y].lower_bound({e.first, 0});
				if(it!=dist[y].end()&&(*it).first==e.first) {
                    if((*it).second<e.second+1) {
                        dist[y].erase(it);
                        dist[y].insert({e.first, e.second+1});
                    }
                } else {
                    dist[y].insert({e.first, e.second+1});
                }
            }
        }
        vector<pair<int, int>> v;
        for(auto y : dist[x])
            v.push_back({y.second, y.first});
        sort(v.begin(), v.end(), greater<pair<int, int>>());
        for(int i=B; i<v.size(); i++)
            dist[x].erase({v[i].second, v[i].first});
    }
    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 [x, dis] : 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: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86