Submission #737260

#	Time	Username	Problem	Language	Result	Execution time	Memory
737260		browntoad	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1839 ms	276508 KiB

bitaro

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
 
const ll maxn = 2e5+5;
const ll inf = (1ll<<60); 
const int iinf = 2147483647;
 
int n, m, qq;
struct quer{
    int nd;
    vector<int> ban;
    int id;
};
vector<int> ans(maxn), topo(maxn), ind(maxn);
vector<int> sz(maxn);
vector<int> tp;
vector<int> graph[maxn];
vector<int> rgraph[maxn];
const int bloc = 310;
pii kth[maxn][bloc+5];
vector<quer> q1, q2;
void init(){
    queue<int> qu;
    int cnt = 1;
    REP1(i, n){
        if (ind[i] == 0){
            qu.push(i);
        }
    }
    while(qu.size()){
        int x = qu.front(); qu.pop();
        topo[x] = cnt;
        tp.pb(x);
        cnt++;
        REP(i, SZ(graph[x])){
            ind[graph[x][i]]--;
            if (ind[graph[x][i]] == 0){
                qu.push(graph[x][i]);
            }
        }
    }
}
void proc1(){
    vector<int> cptr(n+1);
    vector<bool> alr(n+1);
    vector<pii> tmp;
    REP(i, SZ(tp)){
        int x = tp[i], cur;
        pii cmx = {0, x};
        while(1){
            if (sz[x] >= bloc) break;
            cmx = {0, x};
            REP(j, SZ(rgraph[x])){
                cur = rgraph[x][j];
                while(cptr[cur] < sz[cur] && alr[kth[cur][cptr[cur]].s]){
                    cptr[cur]++;
                }
            }
            REP(j, SZ(rgraph[x])){
                cur = rgraph[x][j];
                if (cptr[cur] < sz[cur]){
                    if (kth[cur][cptr[cur]].f+1 > cmx.f){
                        cmx.f = kth[cur][cptr[cur]].f+1;
                        cmx.s = cur;
                    }
                }
            }
            if (cmx.f == 0){
                kth[x][sz[x]] = cmx;
                sz[x]++;
                break;
            }
            cptr[cmx.s]++;
            cmx.s = kth[cmx.s][cptr[cmx.s]-1].s;
            kth[x][sz[x]] = cmx;
            sz[x]++;
            alr[cmx.s] = 1;
        }
        REP(j, SZ(rgraph[x])){
            cptr[rgraph[x][j]] = 0;
        }
        REP(j, sz[x]){
            alr[kth[x][j].s] = 0;
        }
    }
    vector<bool> no(n+1);
    REP(i, SZ(q1)){
        REP(j, SZ(q1[i].ban)){
            no[q1[i].ban[j]] = true;
        }
        int res = iinf;
        REP(j, sz[q1[i].nd]){
            if (no[kth[q1[i].nd][j].s]) continue;
            res = kth[q1[i].nd][j].f;
            break;
        }
        if (res == iinf) res = -1;
        ans[q1[i].id] = res;
        REP(j, SZ(q1[i].ban)){
            no[q1[i].ban[j]] = false;
        }
    }
}
void proc2(){
    vector<int> dis(n+1);
    vector<bool> no(n+1);
    REP(i, SZ(q2)){
        REP(j, SZ(q2[i].ban)){
            no[q2[i].ban[j]] = true;
        }
        REP(j, topo[q2[i].nd]){
            dis[tp[j]] = -iinf;
        }        
        REP(j, topo[q2[i].nd]){
            int x = tp[j];
            if (!no[x]){
                dis[x] = max(dis[x], 0);
            }
            REP(k, SZ(graph[x])){
                if (topo[graph[x][k]] > topo[q2[i].nd]) break; // pruning
                dis[graph[x][k]] = max(dis[x]+1, dis[graph[x][k]]);
            }
        }
        if (dis[q2[i].nd] < 0) dis[q2[i].nd] = -1;
        ans[q2[i].id] = dis[q2[i].nd];
        REP(j, SZ(q2[i].ban)){
            no[q2[i].ban[j]] = false;
        }
    }
}
bool cmp(int a, int b){
    return topo[a]<topo[b];
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>n>>m>>qq;
    REP(i, m){
        int u, v; cin>>u>>v;
        graph[u].pb(v);
        rgraph[v].pb(u);
        ind[v]++;
    }
    init();
    REP1(i, n) {
        sort(ALL(graph[i]), cmp);
    }
    REP(i, qq){
        int ndd;
        cin>>ndd;
        int k; cin>>k;
        vector<int> bban;
        REP(j, k){
            int x; cin>>x;
            bban.pb(x);
        }
        if (SZ(bban)<=bloc-5){
            q1.pb({ndd, bban, i});
        }
        else 
            q2.pb({ndd, bban, i});
    }
    proc1();
    proc2();
    REP(i, qq){
        cout<<ans[i]<<endl;
    }
 
}
/*
12 17 1
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
8 4 1 2 3 4
*/

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