제출 #670431

#제출 시각아이디문제언어결과실행 시간메모리
670431hafoBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2090 ms269632 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 7; const int oo = 1e9 + 69; const int sz = 320; int n, m, q, u, v, t, y, c, id[maxn], d[maxn]; bool vis[maxn]; pa f[sz][maxn], cur[sz]; vector<int> g[maxn], topo, arc[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>m>>q; while(m--) { cin>>u>>v; g[u].pb(v); arc[v].pb(u); } fill_n(vis, n + 1, 0); for(int i = 1; i <= n; i++) for(int j = 0; j < sz; j++) f[j][i] = (j == 0 ? make_pair(0, i):make_pair(-oo, -1)); for(auto u = 1; u <= n; u++) { for(auto v:g[u]) { fill_n(cur, sz, make_pair(-oo, -1)); for(int id = 0, i = 0, j = 0; (id < sz && (i < sz || j < sz));) { auto a = (i >= sz ? make_pair(-1, -1):make_pair(f[i][u].fi + 1, f[i][u].se)), b = (j >= sz ? make_pair(-1, -1):f[j][v]); if((a.se != -1 && vis[a.se]) && (b.se != -1 && !vis[b.se])) { cur[id++] = b; vis[b.se] = 1; i++; j++; } else if((a.se != -1 && !vis[a.se]) && (b.se != -1 && vis[b.se])) { cur[id++] = a; vis[a.se] = 1; i++; j++; } else if((a.se != -1 && vis[a.se]) && (b.se != -1 && vis[b.se])) { i++; j++; } else { if(a.fi < b.fi) { cur[id++] = b; vis[b.se] = 1; j++; } else { cur[id++] = a; vis[a.se]= 1; i++; } } } for(int id = 0; id < sz; id++) { f[id][v] = cur[id]; if(cur[id].se != -1) vis[cur[id].se] = 0; } } } // for(int i = 0; i < sz; i++) cout<<f[i][5].fi<<" "<<f[i][5].se<<"\n"; fill_n(id, n + 1, 0); for(int k = 1; k <= q; k++) { cin>>t>>y; for(int i = 0; i < y; i++) { cin>>c; id[c] = k; } if(y >= sz) { fill_n(d, n + 1, -1); d[t] = 0; int ans = -1; if(id[t] != k) ans = 0; bool ok = 0; for(int u = t; u >= 1; u--) { if(d[u] == -1) continue; for(auto v:arc[u]) { maxi(d[v], d[u] + 1); if(id[v] != k) maxi(ans, d[v]); } } cout<<ans<<"\n"; } else { int ans = -1; for(int i = 0; i < sz; i++) { int u = f[i][t].se; if(u == -1 || id[u] == k || u > t) continue; maxi(ans, f[i][t].fi); } cout<<ans<<"\n"; } } return 0; }

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:96:18: warning: unused variable 'ok' [-Wunused-variable]
   96 |             bool ok = 0;
      |                  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...