제출 #918399

#제출 시각아이디문제언어결과실행 시간메모리
918399ShaShiBitaro’s Party (JOI18_bitaro)C++17
7 / 100
1684 ms524288 KiB
#include <bits/stdc++.h> // #define int long long #define F first #define S second #define pii pair<int, int> #define all(x) x.begin(), x.end() #define kill(x) cout << x << endl, exit(0); #define mp make_pair #define pb push_back #define endl "\n" using namespace std; typedef long long ll; const int MAXN = (int)1e6 + 7; const int MOD = 999999893; const int INF = (int)1e9 + 7; const int SQ = 600; int n, m, t, flag, u, v, w, k, tmp, tmp2, tmp3, tmp4, tmp5, tmp6, ans, q, ans2; int arr[MAXN], cnt2[MAXN], love[MAXN]; bool hate[MAXN], op[MAXN]; vector<pii> vec[MAXN]; vector<int> adj[MAXN]; vector<int> tvec; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for (int i=0; i<m; i++) { cin >> u >> v; adj[v].pb(u); } fill(arr, arr+n+7, -1); for (int i=1; i<=n; i++) { vec[i].pb(mp(0, i)); tvec.clear(); for (int u:adj[i]) { for (auto cur:vec[u]) { if (arr[cur.S] == -1) { arr[cur.S] = cur.F; tvec.pb(cur.S); } else if (cur.F > arr[cur.S]) { arr[cur.S] = cur.F; } } } for (int u:tvec) vec[i].pb(mp(arr[u]+1, u)), arr[u] = -1; sort(all(vec[i]), greater<pii>()); while (vec[i].size() > SQ) vec[i].pop_back(); // cout << "#" << i << endl; // for (auto cur:vec[i]) cout << "@" << cur.F << " " << cur.S << endl; } while (q--) { cin >> v >> w; tvec.clear(); for (int i=0; i<w; i++) { cin >> u; tvec.pb(u); op[u] = 1; } // cout << "!"; if (w < SQ) { ans = -1; for (auto cur:vec[v]) { if (!op[cur.S]) { ans = cur.F; break; } } cout << ans << endl; } else { for (int i=1; i<=v; i++) { love[i] = (op[i]? -1 : 0); for (int u:adj[i]) if (love[u] != -1 && love[u]+1 > love[i]) love[i] = love[u]+1; } cout << love[v] << endl; } for (int i=0; i<w; i++) op[tvec[i]] = 0; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...