제출 #1365682

#제출 시각아이디문제언어결과실행 시간메모리
1365682TsotneSVBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1437 ms143180 KiB
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")


#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 dist[MAXN];

void dfs(int v) {

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

    vi indices;

    for(int i : g[v]) {
        if(!vis[i]) dfs(i);
        
        for(auto [d,u] : cont[i]) {
            if(dist[u] == -1) indices.pb(u);
            dist[u] = max(dist[u],d + 1);
        }
    }

    for(int i : indices) cont[v].pb({dist[i],i});

    sort(all(cont[v]),greater<pii>());
    
    while(sz(cont[v]) > R) cont[v].pop_back();

    for(int i : indices) dist[i] = -1;
}

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 + dist[i]);
    }

    return dist[v] = ret;
}

void solve(int tc = 0){
    cin>>n>>m>>q; memset(dist,-1,sizeof(dist));

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