Submission #1365608

#TimeUsernameProblemLanguageResultExecution timeMemory
1365608TsotneSVBitaro’s Party (JOI18_bitaro)C++20
14 / 100
869 ms351048 KiB
#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=1e5+5,R=100; 
const ll inf=1e9,INF=1e18; 

int n,m,q;
vi g[MAXN]; vector<pii> cont[MAXN];
bool vis[MAXN] = {0},mark[MAXN] = {0}; int maxDist[MAXN] = {0};

void combine(vector<pii> &A,vector<pii> B) {
    for(auto &&[d,u] : B) d++;
    vector<pii> nA;
    merge(all(A),all(B),back_inserter(nA),greater<pii>());
    nA.resize(unique(all(nA)) - nA.begin());
    while(sz(nA) > 2 * R) nA.pop_back();
    swap(A,nA);
}

void dfs(int v) {

    vis[v] = 1; cont[v].pb({0,v});

    for(int i : g[v]) {
        if(!vis[i]) dfs(i);
        combine(cont[v],cont[i]);
    }

}

int farthest(int v) {

    vis[v] = 1;
    int ret = (mark[v] ? -inf : 0);

    for(int i : g[v]) {
        if(!vis[i]) ret = max(ret,1 + farthest(i));
        else ret = max(ret,1 + maxDist[i]);
    }

    return maxDist[v] = ret;
}

void solve(int tc = 0){
    cin>>n>>m>>q;

    while(m--) {
        int u,v; cin>>u>>v;
        g[v].pb(u);
    }

    rep(i,1,n+1) {
        if(!vis[i]) {
            dfs(i);
        }
    }

    while(q--) {
        int t,y; cin>>t>>y; vi C(y);

        for(int &i : C) {
            cin>>i;
            mark[i] = true;
        }

        if(y >= R) {
            rep(i,1,n+1) vis[i] = 0; 
            print(max(-1,farthest(t)));
        } else {

            bool found = 0;

            for(auto [d,u] : cont[t]) {
                if(!mark[u]) {
                    found = true;
                    print(d);
                    break;
                }
            }

            if(!found) print(-1);

        }

        for(int i : C) mark[i] = false;

    }

}

signed main(){

    ios_base::sync_with_stdio(false); cin.tie(0);

    int tc=1;
    //cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...