Submission #568000

#	Time	Username	Problem	Language	Result	Execution time	Memory
568000		hgmhc	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	892 ms	114280 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() {
    scanf("%d%d%d",&n,&m,&q);
    rep(i,1,m) {
        int s, e; scanf("%d%d",&s,&e);
        rdj[e].push_back(s);
    }
    precalc();
    fill(come+1,come+n+1,true);
    rep(_,1,q) {
        int t, y; scanf("%d%d",&t,&y);
        rep(i,1,y) scanf("%d",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);
                }
            }
            printf("%d\n",max(dp[t],-1));
        } else {
            int answer = -1e9;
            for (const auto &[dist,from] : distances[t]) {
                if (come[from]) {
                    answer = dist;
                    break;
                }
            }
            printf("%d\n",max(answer,-1));
        }
        rep(i,1,y) come[c[i]] = true;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:49:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         int s, e; scanf("%d%d",&s,&e);
      |                   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         int t, y; scanf("%d%d",&t,&y);
      |                   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:56:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         rep(i,1,y) scanf("%d",c+i), come[c[i]] = false;
      |                    ~~~~~^~~~~~~~~~

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