Submission #1182746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182746		peteza	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1701 ms	376240 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int sq = 405;

int n, m, q, a, b;
vector<int> adj[100005], fwd[100005];
vector<pii> cands[100005];
//size of cands[] <= sq ig
bool viscands[100005];
bool visres[100005];
bool visdfs[100005];
int distdfs[100005];

void calccands(int x) {
    if(viscands[x]) return;
    viscands[x] = 1;
    cands[x].emplace_back(0, x);
    for(auto &e:adj[x]) {
        //merge cands[x] with cands[e]
        calccands(e);
        for(auto &E:cands[e]) E.first++;
        vector<pii> res;
        int i=0, j=0;
        for(int cp = 0; cp < cands[e].size() + cands[x].size(); cp++) {
            if(i == cands[x].size()) res.emplace_back(cands[e][j++]);
            else if(j == cands[e].size()) res.emplace_back(cands[x][i++]);
            else {
                if(cands[x][i] > cands[e][j]) res.emplace_back(cands[x][i++]);
                else res.emplace_back(cands[e][j++]);
            }
        }
        vector<pii> realres;
        for(auto &e:res) {
            if(visres[e.second]) continue;
            visres[e.second] = 1;
            realres.emplace_back(e);
        }
        cands[x] = realres;
        if(cands[x].size() > sq) cands[x].resize(sq);
        for(auto &e:res) visres[e.second] = 0;
        for(auto &E:cands[e]) E.first--;
    }
    //dunn!!
}

int dfsfrom(int x) {
    if(visdfs[x]) return distdfs[x];
    visdfs[x] = 1; distdfs[x] = -1;
    for(int &e:fwd[x]) {
        if(dfsfrom(e) != -1) distdfs[x] = max(distdfs[x], distdfs[e]+1);
    }
    return distdfs[x];
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> q;
    while(m--) {
        cin >> a >> b;
        adj[b].push_back(a);
        fwd[a].push_back(b);
    }
    for(int i=1;i<=n;i++) {
        calccands(i);
    }
    while(q--) {
        cin >> b >> a;
        vector<int> qrs(a);
        for(int &e:qrs) {cin >> e; visres[e] = 1;}
        if(a < sq) {
            int ans = -1;
            for(int i=0;i<cands[b].size();i++) {
                if(!visres[cands[b][i].second]) {
                    ans = cands[b][i].first;
                    break;
                }
            }
            cout << ans << '\n';
        } else {
            memset(visdfs, 0, sizeof visdfs);
            visdfs[b] = 1; distdfs[b] = 0;
            for(int i=b;i>=1;i--) {
                //cout << dfsfrom(i);
                dfsfrom(i);
            }
            int ans = -1;
            for(int i=1;i<=b;i++) {
                if(!visres[i] && (distdfs[i] != -1)) /*cout << i << ", ",*/ ans = max(ans, distdfs[i]);
            }
            cout << ans << '\n';
        }
        for(int &e:qrs) {visres[e] = 0;}
    }
}

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