제출 #568001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568001		hgmhc	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	885 ms	110756 KiB

bitaro

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1e5+3, B = 100;
int n, m, q;
vector<int> rdj[N];
int dp[N], c[N];
bool come[N];
vector<ii> distances[N];

#define D first
#define F second

void precalc() {
    bool used[N] {0,};
    rep(i,1,n) {
        for (int j : rdj[i]) {
            auto &x = distances[i], &y = distances[j];
            vector<ii> tmp; // tmp <- x + y
            int a = 0, b = 0;
            while (a < size(x) or b < size(y)) {
                if (a >= size(x) or (b < size(y) and y[b].D+1 >= x[a].D)) {
                    if (!used[y[b].F]) tmp.emplace_back(y[b].D+1,y[b].F);
                    used[y[b].F] = true;
                    b++;
                }
                else if (b >= size(y) or (a < size(x) and x[a].D > y[b].D+1)) {
                    if (!used[x[a].F]) tmp.emplace_back(x[a].D,x[a].F);
                    used[x[a].F] = true;
                    a++;
                }
                if (size(tmp) == B) break;
            }
            for (ii t : tmp) used[t.F] = false; // used 복구
            swap(distances[i],tmp); // distances[i] <- tmp
        }
        if (size(distances[i]) < B) distances[i].emplace_back(0,i);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    rep(i,1,m) {
        int s, e; cin >> s >> e;
        rdj[e].push_back(s);
    }
    precalc();
    fill(come+1,come+n+1,true);
    rep(_,1,q) {
        int t, y; cin >> t >> y;
        rep(i,1,y) cin >> c[i], come[c[i]] = false;
        if (y >= B) {
            rep(i,1,t) {
                dp[i] = -1e9;
                if (come[i]) Mup(dp[i],0);
                for (const int &j : rdj[i]) {
                    Mup(dp[i],dp[j]+1);
                }
            }
            cout << max(dp[t],-1) << '\n';
        } else {
            int answer = -1e9;
            for (const auto &[dist,from] : distances[t]) {
                if (come[from]) {
                    answer = dist;
                    break;
                }
            }
            cout << max(answer,-1) << '\n';
        }
        rep(i,1,y) come[c[i]] = true;
    }
}

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