Submission #1193792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193792		ortsac	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2078 ms	312124 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fst first
#define snd second
using namespace std;
 
vector<vector<int>> adj;
vector<vector<int>> rAdj;
vector<vector<pair<int,int>>> yth;
 
vector<pair<int,int>> aux;
vector<int> vst;
void merge(int i, int j) {
    aux.clear();
    int l=0, maxl = yth[i].size()-1;
    int r=0, maxr = yth[j].size()-1;
    for (auto& u : yth[i]) u.first++;
    vst.clear(), vst.resize(i+1,0);
 
    int f, s;
    while(aux.size()<=301) {
        if(l<=maxl and r<=maxr) {
            if(yth[i][l].fst > yth[j][r].fst) {
                f=yth[i][l].fst, s=yth[i][l].snd;
                if(!vst[s]) {
                    vst[s]=1;
                    aux.pb({f,s});
                }
                l++;
            } else {
                f=yth[j][r].fst, s=yth[j][r].snd;
                if(!vst[s]) {
                    vst[s]=1;
                    aux.pb({f,s});
                }
                r++;
            }
        } else if(l<=maxl) {
            f=yth[i][l].fst, s=yth[i][l].snd;
            if(!vst[s]) {
                vst[s]=1;
                aux.pb({f,s});
            }
            l++;
        } else if(r<=maxr) {
            f=yth[j][r].fst, s=yth[j][r].snd;
            if(!vst[s]) {
                vst[s]=1;
                aux.pb({f,s});
            }
            r++;
        } else break;
    }
    yth[j]=aux;
    for (auto& u : yth[i]) u.first--;
}
void precalc(int n) {
    for(int x=1; x<=n; ++x) {
        if (((int) yth[x].size()) < 301) yth[x].pb({0,x});
        for(int y : rAdj[x]) {
            merge(x,y);
        }
    }
}
 
vector<int> busy;
int solve(int t) {
    for(int i=0; i<=(yth[t].size()-1); ++i) {
        if(!busy[yth[t][i].snd]) return yth[t][i].fst;
    }
    return -1;
}
vector<int> d;
int brute(int t, int n) {
    d.clear();
    d.resize(n + 1, -1);
    int ans = -1;
    d[t] = 0;
    for (int i = n; i >= 1; i--) {
        if (d[i] == -1) continue; // t nem chegou aqui
        for (auto u : adj[i]) d[u] = max(d[u], d[i] + 1);
        if (!busy[i]) ans = max(ans, d[i]);
    }
    return ans;
}
 
int32_t main() {
    int n, m, q; cin >> n >> m >> q;
    adj.resize(n+1); yth.resize(n+1); rAdj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[b].pb(a);
        rAdj[a].pb(b);
    }
    precalc(n);
    //for (int i = 1; i <= n; i++) {
    //    cout << i << "\n";
    //    for (auto u : yth[i]) cout << u.first << " " << u.second << "\n";
    //}
    //cout << "Oi\n";
    busy.resize(n+1,0);
    while(q--) {
        int t, y;
        cin >> t >> y;
        vector<int> currBusy;
        for(int i=0; i<y; ++i) {
            int a;
            cin >> a;
            currBusy.push_back(a);
            busy[a]=1;
        }
 
        if(y<=300) cout << solve(t) << endl;
        else cout << brute(t, n) << endl;
        // if(brute(t)!=solve(t)) {
        //     cout << t << endl;
        //     // for(int i=1; i<=n; ++i) {
        //     //     for(int j : adj[i]) cout << j << " ";
        //     //     if(!adj[i].empty()) cout << endl << i << endl;
        //     // }
        //     for(int i=1; i<=n; ++i) {
        //         if(busy[i]) cout << i << " ";
        //     }
        //     cout << endl;
        //     cout << "opa, aq amigao: " << brute(t) << " " << solve(t) << endl;
        // } else cout << "auuuh " << solve(t) << endl;
        
        for (auto u : currBusy) busy[u] = 0;
    }
}

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