# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95470 | 2019-02-01T13:00:53 Z | Retro3014 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 102208 KB |
#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <math.h> #include <queue> using namespace std; #define MAX_N 100000 int N, M, Q; int Y, SQ; vector<int> gp[MAX_N+1]; struct S{ S (int idx, int data) : idx(idx), data(data) {} int idx, data; bool operator <(const S &a)const{ if(data==a.data){ return idx<a.idx; } return data<a.data; } }; vector<S> vt[MAX_N+1]; struct QUERY{ int t, y; vector<int> c; }; vector<QUERY> Query; bool chk[MAX_N+1]; int dist[MAX_N+1]; void solve_query(QUERY now){ for(int i=0; i<now.y; i++){ chk[now.c[i]] = true; } if(now.y>=SQ){ int ans = -1; for(int i = now.t; i>=1; i--){ if(i!=now.t && dist[i]==0){ continue; } if(!chk[i]){ ans = max(ans, dist[i]); } for(int j=0; j<gp[i].size(); j++){ dist[gp[i][j]] = max(dist[gp[i][j]], dist[i]+1); } dist[i] = 0; } printf("%d\n", ans); }else{ int idx = 0; while(idx<vt[now.t].size()){ if(chk[vt[now.t][idx].idx]) idx++; else break; } if(idx==vt[now.t].size()) printf("-1\n"); else printf("%d\n", vt[now.t][idx].data); } for(int i=0; i<now.y; i++){ chk[now.c[i]] = false; } } priority_queue<S> pq; void solve(){ SQ = sqrt(Y); for(int i=1; i<=N; i++){ pq.push({i, 0}); //vt[i].push_back({i, 0}); for(int j=0; j<gp[i].size(); j++){ for(int k=0; k<vt[gp[i][j]].size(); k++){ pq.push({vt[gp[i][j]][k].idx, vt[gp[i][j]][k].data+1}); } } int cnt = 0; while(!pq.empty() && cnt<SQ){ S now = pq.top(); pq.pop(); if(!chk[now.idx]){ cnt++; chk[now.idx] = true; vt[i].push_back(now); } }for(int j=0; j<vt[i].size(); j++){ chk[vt[i][j].idx] = false; } /*for(int j=1; j<=N; j++){ chk[j] = false; }*/ } } int main(){ scanf("%d%d%d", &N, &M, &Q); for(int i=0; i<M; i++){ int a, b; scanf("%d%d", &a, &b); gp[b].push_back(a); } for(int i=0; i<Q; i++){ QUERY tmp; scanf("%d%d", &tmp.t, &tmp.y); Y+=tmp.y; while(!tmp.c.empty()) tmp.c.pop_back(); for(int i=0; i<tmp.y; i++){ int x; scanf("%d", &x); tmp.c.push_back(x); } Query.push_back(tmp); } //cout<<1<<endl; solve(); for(int i=0; i<Query.size(); i++){ solve_query(Query[i]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 11 ms | 5368 KB | Output is correct |
6 | Correct | 11 ms | 5368 KB | Output is correct |
7 | Correct | 11 ms | 5368 KB | Output is correct |
8 | Correct | 10 ms | 5496 KB | Output is correct |
9 | Correct | 10 ms | 5496 KB | Output is correct |
10 | Correct | 10 ms | 5496 KB | Output is correct |
11 | Correct | 10 ms | 5496 KB | Output is correct |
12 | Correct | 13 ms | 5388 KB | Output is correct |
13 | Correct | 10 ms | 5624 KB | Output is correct |
14 | Correct | 12 ms | 5500 KB | Output is correct |
15 | Correct | 9 ms | 5368 KB | Output is correct |
16 | Correct | 9 ms | 5500 KB | Output is correct |
17 | Correct | 9 ms | 5496 KB | Output is correct |
18 | Correct | 10 ms | 5496 KB | Output is correct |
19 | Correct | 11 ms | 5624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 11 ms | 5368 KB | Output is correct |
6 | Correct | 11 ms | 5368 KB | Output is correct |
7 | Correct | 11 ms | 5368 KB | Output is correct |
8 | Correct | 10 ms | 5496 KB | Output is correct |
9 | Correct | 10 ms | 5496 KB | Output is correct |
10 | Correct | 10 ms | 5496 KB | Output is correct |
11 | Correct | 10 ms | 5496 KB | Output is correct |
12 | Correct | 13 ms | 5388 KB | Output is correct |
13 | Correct | 10 ms | 5624 KB | Output is correct |
14 | Correct | 12 ms | 5500 KB | Output is correct |
15 | Correct | 9 ms | 5368 KB | Output is correct |
16 | Correct | 9 ms | 5500 KB | Output is correct |
17 | Correct | 9 ms | 5496 KB | Output is correct |
18 | Correct | 10 ms | 5496 KB | Output is correct |
19 | Correct | 11 ms | 5624 KB | Output is correct |
20 | Correct | 225 ms | 39228 KB | Output is correct |
21 | Correct | 223 ms | 39356 KB | Output is correct |
22 | Correct | 236 ms | 39228 KB | Output is correct |
23 | Correct | 252 ms | 72216 KB | Output is correct |
24 | Execution timed out | 2044 ms | 102208 KB | Time limit exceeded |
25 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 11 ms | 5368 KB | Output is correct |
6 | Correct | 11 ms | 5368 KB | Output is correct |
7 | Correct | 11 ms | 5368 KB | Output is correct |
8 | Correct | 10 ms | 5496 KB | Output is correct |
9 | Correct | 10 ms | 5496 KB | Output is correct |
10 | Correct | 10 ms | 5496 KB | Output is correct |
11 | Correct | 10 ms | 5496 KB | Output is correct |
12 | Correct | 13 ms | 5388 KB | Output is correct |
13 | Correct | 10 ms | 5624 KB | Output is correct |
14 | Correct | 12 ms | 5500 KB | Output is correct |
15 | Correct | 9 ms | 5368 KB | Output is correct |
16 | Correct | 9 ms | 5500 KB | Output is correct |
17 | Correct | 9 ms | 5496 KB | Output is correct |
18 | Correct | 10 ms | 5496 KB | Output is correct |
19 | Correct | 11 ms | 5624 KB | Output is correct |
20 | Correct | 225 ms | 39228 KB | Output is correct |
21 | Correct | 223 ms | 39356 KB | Output is correct |
22 | Correct | 236 ms | 39228 KB | Output is correct |
23 | Correct | 252 ms | 72216 KB | Output is correct |
24 | Execution timed out | 2044 ms | 102208 KB | Time limit exceeded |
25 | Halted | 0 ms | 0 KB | - |