Submission #1345292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345292		light2901	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	326 ms	89112 KiB

bitaro

#include <bits/stdc++.h>
#define el cout<<"\n";
using namespace std;
using ll = long long;
#define fi first
#define se second
const int MAXN = 1e5 + 5;
const int BL = 100;

int n, m, q, dd[MAXN], dp[MAXN], ddau[MAXN], ans, tt[MAXN];
int step_id = 0;
vector<int> g[MAXN];
vector<pair<int, int>> luu[MAXN];
main(void) {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) {
        luu[i].push_back({0, i});
        for(int v : g[i]) {
            step_id++; 
            vector<pair<int, int>> merged;
            int p1 = 0, p2 = 0;
            while(merged.size() < BL && (p1 < luu[i].size() || p2 < luu[v].size())) {
                if(p1 < luu[i].size() && (p2 == luu[v].size() || luu[i][p1].fi >= luu[v][p2].fi + 1)) {
                    if(tt[luu[i][p1].se] != step_id) {
                        tt[luu[i][p1].se] = step_id; 
                        merged.push_back(luu[i][p1]);
                    }
                    p1++;
                }else {
                    if(tt[luu[v][p2].se] != step_id) {
                        tt[luu[v][p2].se] = step_id; 
                        merged.push_back({luu[v][p2].fi + 1, luu[v][p2].se});
                    }
                    p2++;
                }
            }
            luu[i] = merged;
        }
    }
    for(int i = 1; i <= q; i++) {
        vector<int> res;
        int u, sl; cin >> u >> sl;
        for(int j = 1; j <= sl; j++) {
            int x; cin >> x;
            ddau[x] = 1;
            res.push_back(x);
        }
        if(sl >= BL) {
            for(int j = 1; j <= u; j++) {
                dp[j] = -1e9; 
                if(ddau[j] == 0) dp[j] = 0; 
                for(int v : g[j]) {
                    if(dp[v] != -1e9) {
                        dp[j] = max(dp[j], dp[v] + 1);
                    }
                }
            }
            if(dp[u] < 0) cout << -1;
            else cout << dp[u];
            el;
        }else {
            int ok = 1;
            for(auto x : luu[u]) if(ddau[x.se] == 0) {
                cout << x.fi; el;
                ok = 0;
                break;
            }
            if(ok) {
                cout << -1; el;
            }
        }
        for(auto y : res) ddau[y] = 0;
    }
    
    return 0;
}
// T.T<33~~

Compilation message (stderr)

bitaro.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main(void) {
      | ^~~~

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