제출 #46864

#제출 시각아이디문제언어결과실행 시간메모리
46864kyleliuBitaro’s Party (JOI18_bitaro)C++14
7 / 100
2048 ms14200 KiB
#include <bits/stdc++.h> // PLEASE using namespace std; typedef long long ll; typedef long double ld; typedef pair <int, int> pp; #define MAXN 100005 #define MAXM 1005 #define MAXP 25 #define A first #define B second #define MP make_pair #define PB push_back const ll INF = 2e9+13; const ll MOD = 1e9+7; const int K = 320; int N, M, Q; vector <pp> farth[MAXN]; vector <int> f[MAXN]; vector <int> g[MAXN]; int in[MAXN]; int dp[MAXN]; bool can[MAXN]; bool vis[MAXN]; void solve() { queue <int> q; memset(vis, 0, sizeof(vis)); for(int i=1; i<=N; i++) { dp[i] = -1; if(in[i] == 0) { q.push(i); if(can[i]) dp[i] = 0; } } while(!q.empty()) { int u = q.front(); q.pop(); if(can[u]) dp[u] = max(dp[u], 0); if(vis[u]) continue; vis[u] = 1; for(auto v : g[u]) { if(dp[u] >= 0) dp[v] = max(dp[v], dp[u] + 1); in[v]--; if(in[v] == 0) q.push(v); } } for(int i=1; i<=N; i++) for(auto v : g[i]) in[v]++; } bool cmp(pp a, pp b) { return a.A > b.A; } void pre() { queue <int> q; memset(vis, 0, sizeof(vis)); for(int i=1; i<=N; i++) { if(in[i] == 0) { q.push(i); farth[i].PB({0, i}); } } while(!q.empty()) { int u = q.front(); q.pop(); if(vis[u]) continue; vis[u] = 1; for(auto v : g[u]) { in[v]--; if(in[v] == 0) if(!vis[v]) q.push(v); } // merge it vector <pp> ret; ret.PB({0, u}); for(auto v : f[u]) for(auto e : farth[v]) ret.PB({e.A+1, e.B}); sort(ret.begin(), ret.end(), cmp); for(int i=0; i<min(K, (int)ret.size()); i++) farth[u].PB(ret[i]); } for(int i=1; i<=N; i++) for(auto v : g[i]) in[v]++; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> M >> Q; for(int i=1; i<=N; i++) can[i] = 1; for(int i=0; i<M; i++) { int a, b; cin >> a >> b; g[a].PB(b); in[b]++; f[b].PB(a); } pre(); while(Q--) { int t, n; cin >> t >> n; if(n > K) { vector <int> v; for(int i=1; i<=n; i++) { int x; cin >> x; v.PB(x); } for(auto x : v) can[x] = 0; solve(); cout << dp[t] << endl; for(auto x : v) can[x] = 1; } else { vector <int> v; for(int i=1; i<=n; i++) { int x; cin >> x; v.PB(x); } for(auto x : v) can[x] = 0; bool printed = 0; //cout << "TARG " << t << endl; for(auto x : farth[t]) { // cout << "DIST " << x.A << " NODE " << x.B << endl; if(can[x.B]) { cout << x.A << endl; printed = 1; break; } } if(!printed) cout << -1 << endl; for(auto x : v) can[x] = 1; } } }

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

bitaro.cpp: In function 'void solve()':
bitaro.cpp:39:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(vis[u]) continue; vis[u] = 1;
   ^~
bitaro.cpp:39:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(vis[u]) continue; vis[u] = 1;
                        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...