제출 #1365538

#제출 시각아이디문제언어결과실행 시간메모리
1365538TsotneSVBitaro’s Party (JOI18_bitaro)C++20
0 / 100
2097 ms70516 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=350; 
const ll inf=1e9,INF=1e18; 

int n,m,q,timer = 2;
vi g[MAXN]; deque<pii> cont[MAXN];
int vis[MAXN] = {0};

void combine(deque<pii> &A,deque<pii> &B) {

    int lA = 0,lB = 0; deque<pii> nA;

    while(sz(nA) < R and (lA != sz(A) or lB != sz(B))) {
        
        if(lA != sz(A) and (lB == sz(B) or A[lA].fi >= B[lB].fi + 1)) {
            nA.pb(A[lA++]);
        } else if(lB != sz(B) and (lA == sz(A) or A[lA].fi < B[lB].fi + 1)) {
            nA.pb(B[lB++]);
            nA.back().fi++;
        }

    }

    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) {

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

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

    return 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;

        rep(i,0,y) {
            int u; cin>>u;
            vis[u] = timer;
        }

        if(y >= R) {
            print(max(-1,farthest(t)));
        } else {

            bool found = 0;

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

            if(!found) print(-1);

        }

        timer++;
    }

}

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);
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…