Submission #1345283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345283		light2901	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2092 ms	2112 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;
vector<int> g[MAXN];
vector<pair<int, int>> luu[MAXN];
void dfs(int u) {
    for(int v : g[u]) {
        dfs(v);
        vector<pair<int, int>> tem;
        for(auto x : luu[v]) luu[u].push_back({x.fi + 1, x.se});
        sort(luu[u].rbegin(), luu[u].rend());
        while(luu[u].size() > BL) luu[u].pop_back();
    }
}
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 i = 1; i <= n; i++) if(!dd[i]) {
        dfs(i);
    }
    for(int i = 1; i <= q; i++) {
        vector<int> res;
        int u, sl; cin >> u >> sl;
        for(int i = 1; i <= sl; i++) {
            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;
                for(auto y : res) ddau[y] = 0;
                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:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(void) {
      | ^~~~

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