제출 #530397

#제출 시각아이디문제언어결과실행 시간메모리
530397akhan42Bitaro’s Party (JOI18_bitaro)C++17
0 / 100
53 ms12928 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define all(v) v.begin(), v.end() #define min3(a, b, c) min(a, min(b, c)) #define at(m, k) (m.find(k) != m.end() ? m[k]: 0) typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } const int MX = 100 * 1000 + 10; int sq = 1010; vi gr[MX]; vii farthest[MX]; bool busy[MX]; bool att[MX]; vi d1; int dfs1(int node) { if(d1[node] != -1) return d1[node]; int mx = 0; for(int nb: gr[node]) { if(busy[nb]) { int val = dfs1(nb); if(val) maxeq(mx, val + 1); } else maxeq(mx, dfs1(nb) + 1); } d1[node] = mx; return mx; } void dfs2(int node) { if(att[node]) return; att[node] = true; vii ans; ans.eb(0, node); for(int nb: gr[node]) { dfs2(nb); for(ii p: farthest[nb]) ans.eb(p.F + 1, p.S); } sort(all(ans), greater<ii>()); for(int i = 0; i < sq && i < sz(ans); i++) farthest[node].pb(ans[i]); } void solve() { int n, m, q; cin >> n >> m >> q; forn(_, m) { int a, b; cin >> a >> b; gr[b].pb(a); } forbn(node, 1, n + 1) dfs2(node); forn(_, q) { int t, Y; cin >> t >> Y; vi ys(Y); forn(j, Y) { cin >> ys[j]; busy[ys[j]] = true; } if(Y >= sq && false) { d1.assign(n + 1, -1); int val = dfs1(t); if(val == 0 && busy[t]) cout << -1 << '\n'; else cout << val << '\n'; } else { bool printed = false; for(ii node: farthest[t]) { if(!busy[node.S]) { cout << node.F << '\n'; printed = true; break; } } if(!printed) cout << -1 << '\n'; } for(int y: ys) busy[y] = false; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("haybales.in", "r", stdin); // freopen("haybales.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...