제출 #1103550

#제출 시각아이디문제언어결과실행 시간메모리
1103550underwaterkillerwhaleBitaro’s Party (JOI18_bitaro)C++17
100 / 100
984 ms519780 KiB
#include <bits/stdc++.h> #define int long long #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e5 + 2; const int Mod = 1e9 + 7;///lon const int INF = 2e9; const ll BASE = 137; const int szBL = 320; int n, m, Q; vector<int> ke[N], ivke[N]; vector<pii> dp[N]; int vis[N]; int dd[N]; int f[N]; void solution () { cin >> n >> m >> Q; rep (i, 1, m) { int u, v; cin >> u >> v; ke[v].pb(u); } vector<int> topo; { function<void(int)> dfs = [&] (int u) { vis[u] = 1; iter (&v, ke[u]) { if (!vis[v]) { dfs(v); } } vis[u] = 2; topo.pb(u); }; rep (i, 1, n) if (!vis[i]) dfs(i); } auto combine = [] (vector<pii> &A, vector<pii> &B) { static vector<pii> C; C.clear(); int pA = 0, pB = 0; while ((pA < SZ(A) || pB < SZ(B)) && SZ(C) < szBL) { if (pA == SZ(A)) { if (!dd[B[pB].se]) C.pb({B[pB].fs + 1, B[pB].se}); dd[B[pB].se] = 1; ++pB; } else if (pB == SZ(B)) { if (!dd[A[pA].se]) C.pb(A[pA]); dd[A[pA].se] = 1; ++pA; } else { if (A[pA].fs > B[pB].fs + 1) { if(!dd[A[pA].se]) C.pb(A[pA]); dd[A[pA].se] = 1; ++pA; } else { if (!dd[B[pB].se]) C.pb({B[pB].fs + 1, B[pB].se}); dd[B[pB].se] = 1; ++pB; } } } A = C; iter (&id, C) dd[id.se] = 0; }; iter (&u, topo) { dp[u].pb({0, u}); iter (&v, ke[u]) combine(dp[u], dp[v]); } rep (q, 1, Q) { int T, Y; cin >> T >> Y; static int step = 0; ++step; rep (i, 1, Y) { int X; cin >> X; dd[X] = step; } if (Y < szBL) { bool ok = 0; iter (&id, dp[T]) { if (dd[id.se] != step) { cout << id.fs <<"\n"; ok = 1; break; } } if (!ok) { cout << -1 <<"\n"; } } else { reb (i, n, 1) { int u = topo[i - 1]; if (u == T) f[u] = 1; if (!f[u]) continue; iter (&v, ke[u]) f[v] = max(f[v], f[u] + 1); } int res = 0; rep (i, 1, n) if (dd[i] != step) res = max(res, f[i]); cout << res - 1 <<"\n"; rep (i, 1, n) { f[i] = 0; } } } } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); main () { // file("creature"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +12 */

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp:135:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  135 | main () {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...