제출 #1365694

#제출 시각아이디문제언어결과실행 시간메모리
1365694TsotneSVBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1492 ms134860 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 combine(vector<pii> &A,vector<pii> &B) {

    vi nodes;

    for(auto &&[d,u] : A) {
        if(dist[u] == -1) nodes.pb(u);
        dist[u] = max(dist[u],d);
    }

    for(auto &&[d,u] : B) {
        if(dist[u] == -1) nodes.pb(u);
        dist[u] = max(dist[u],d + 1);
    }

    A.clear();

    for(int i : nodes) A.pb({dist[i],i});

    sort(all(A),greater<pii>());

    while(sz(A) > R) A.pop_back();

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

}

void dfs(int v) {

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

    vi indices;

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