Submission #736589

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

bitaro

#include <bits/stdc++.h>
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> tp;
vector<int> graph[maxn];
vector<pii> kth[maxn];
const int bloc = 75;
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(){
    REP1(i, n) kth[i].pb({0, i});
    REP(i, SZ(tp)){
        int x = tp[i];
        sort(ALL(kth[x]));
        reverse(ALL(kth[x]));
        REP(j, SZ(graph[x])){
            REP(l, min(SZ(kth[x]), bloc)){
                kth[graph[x][j]].pb({kth[x][l].f+1, kth[x][l].s});
            }
        }
    }
    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(kth[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);
        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);
        }
        sort(ALL(bban));
        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;
    }
 
}
 

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