제출 #1020121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1020121		dosts	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	6 ms	9308 KiB

bitaro

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;
const int N = 1e5+1,inf = 1e18,MOD = 998244353,B = 350; 
                 
vi edges[N],egdes[N];
vector<pii> mfs[N];
vi vis(N,0);
vi best(N);

void bfs(int root) {
    queue<int> q;
    q.push(root);
    vi lazy;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        vis[node] = 1;
        lazy.push_back(node);
        vector<pii> ps;
        vi allnbs;
        for (auto it : egdes[node]) {
            for (auto itt : mfs[it]) {
                if (!best[itt.ss]) allnbs.push_back(itt.ss);
                best[itt.ss] = max(best[itt.ss],itt.ff+1);
            }
        }
        for (auto it : allnbs) ps.push_back({best[it],it});
        if (!ps.empty()) sort(all(ps),greater<pii>());
        if (ps.size() > B+5) ps.resize(B+5);
        swap(mfs[node],ps);
        mfs[node].push_back({0,node});
        for (auto it : egdes[node]) for (auto itt : mfs[it]) best[itt.ss] = 0;
        for (auto it : edges[node]) if (!vis[it]) q.push(it);
    }
}

vector<pii> vv;

void dfs2(int node,int d = 0) {
    if (vis[node]) return;
    vis[node] = 1;
    vv.push_back({node,d});
    for (auto it : egdes[node]) dfs2(it,d+1);
}

void solve() {                             
    int n,m,q;
    cin >> n >> m >> q;
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        egdes[b].push_back(a);
    }

    for (int i=1;i<=n;i++) {
        if (egdes[i].size()) continue;
        bfs(i);
    }
    vi banned(n+1,0);
    while (q--) {
        int node,k;
        cin >> node >> k;
        vi c(k+1);
        for (int i=1;i<=k;i++) cin >> c[i];
        for (int i=1;i<=k;i++) banned[c[i]] = 1;
        if (k <= B) {
            bool fl = 0;
            for (auto it : mfs[node]) {
                if (!banned[it.ss]) {
                    fl = 1;
                    cout << it.ff << endl;
                    break;
                }
            }
            if (!fl) cout << -1 << endl;
        }
        else {
            vis.assign(n+1,0);
            dfs2(node);
            int ans = -1;
            for (auto it : vv) {
                if (!banned[it.ff]) ans= max(ans,it.ss);
            }
            vv.clear();
            cout << ans << '\n';
        }
        for (int i=1;i<=k;i++) banned[c[i]] = 0;
    }
}   
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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