제출 #1277295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277295		dwuy	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1016 ms	258680 KiB

bitaro

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
using pii = pair<int, int>;

const int MX = 100005;
int n, m, q, B;
int f[MX];
bitset<MX> vist = 0;
vector<int> G[MX];
vector<pii> T[MX];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    B = sqrt(n);
    for(int i=1; i<=m; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    vist = 0;
    for(int i=1; i<=n; i++) T[i].push_back({0, i});
    for(int u=1; u<=n; u++){
        for(int v: G[u]){
            if(T[v].size() == 0) T[v] = T[u];
            else{
                vector<pii> vt;
                for(int i=0, j=0; vt.size() <= B && (i < (int)T[u].size() || j < (int)T[v].size());){
                    if(i < (int)T[u].size() && j < T[v].size()){
                        pii x = T[u][i]; x.fi++;
                        pii y = T[v][j]; 
                        if(vist[x.se]) { i++; continue; }
                        if(vist[y.se]) { j++; continue; }
                        if(x > y){
                            vist[x.se] = 1;
                            vt.push_back(x);
                            i++;
                        }
                        else{
                            vist[y.se] = 1;
                            vt.push_back(y);
                            j++;
                        }
                    }
                    else if(i < (int)T[u].size()){
                        pii x = T[u][i]; x.fi++;
                        if(vist[x.se]) { i++; continue; }
                        vist[x.se] = 1;
                        vt.push_back(x);
                        i++;
                    }
                    else if(j < (int)T[v].size()){
                        pii y = T[v][j]; 
                        if(vist[y.se]) { j++; continue; }
                        vist[y.se] = 1;
                        vt.push_back(y);
                        j++;
                    }
                    else break;
                }
                T[v] = vt;
                for(pii x: vt) vist[x.se] = 0;
            }
        }
    }

    for(int i=1; i<=q; i++){
        int S, k;
        cin >> S >> k;
        vector<int> vt(k);
        for(int &x: vt) cin >> x;
        if(vt.size() > B){
            vist = 0;
            for(int &x: vt) vist[x] = 1;
            memset(f, -0x3f, sizeof f);
            for(int u=1; u<=n; u++){
                if(!vist[u]) f[u] = max(f[u], 0);
                for(int v: G[u]) f[v] = max(f[v], f[u] + 1);
            }
            if(f[S] < 0) cout << -1 << '\n';
            else cout << f[S] << '\n';
            for(int &x: vt) vist[x] = 0;
        }
        else{
            for(int x: vt) vist[x] = 1;
            int ans = -1;
            for(pii p: T[S]) if(!vist[p.se]){
                ans = p.fi;
                break;
            }
            for(int x: vt) vist[x] = 0;
            cout << ans << '\n';
        }
    }

    return 0;
}

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