# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95469 | 2019-02-01T12:54:11 Z | Retro3014 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 214408 KB |
#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <math.h> 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; } } void solve(){ SQ = sqrt(Y); for(int i=1; i<=N; i++){ 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++){ vt[i].push_back({vt[gp[i][j]][k].idx, vt[gp[i][j]][k].data+1}); } } sort(vt[i].begin(), vt[i].end()); int index = 0, cnt = 0; while(index<vt[i].size() && cnt<SQ){ if(!chk[vt[i][index].idx]){ cnt++; chk[vt[i][index].idx] = true; }else{ vt[i][index].data = -1; } index++; } sort(vt[i].begin(), vt[i].end()); while(vt[i].size()>SQ || vt[i].back().data==-1) vt[i].pop_back(); 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 | 6 ms | 5112 KB | Output is correct |
3 | Correct | 5 ms | 5112 KB | Output is correct |
4 | Correct | 5 ms | 4984 KB | Output is correct |
5 | Correct | 8 ms | 5496 KB | Output is correct |
6 | Correct | 8 ms | 5368 KB | Output is correct |
7 | Correct | 10 ms | 5496 KB | Output is correct |
8 | Correct | 7 ms | 5624 KB | Output is correct |
9 | Correct | 9 ms | 5624 KB | Output is correct |
10 | Correct | 8 ms | 5624 KB | Output is correct |
11 | Correct | 9 ms | 5624 KB | Output is correct |
12 | Correct | 9 ms | 5488 KB | Output is correct |
13 | Correct | 10 ms | 5624 KB | Output is correct |
14 | Correct | 8 ms | 5496 KB | Output is correct |
15 | Correct | 9 ms | 5368 KB | Output is correct |
16 | Correct | 9 ms | 5496 KB | Output is correct |
17 | Correct | 9 ms | 5496 KB | Output is correct |
18 | Correct | 12 ms | 5368 KB | Output is correct |
19 | Correct | 9 ms | 5496 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5112 KB | Output is correct |
3 | Correct | 5 ms | 5112 KB | Output is correct |
4 | Correct | 5 ms | 4984 KB | Output is correct |
5 | Correct | 8 ms | 5496 KB | Output is correct |
6 | Correct | 8 ms | 5368 KB | Output is correct |
7 | Correct | 10 ms | 5496 KB | Output is correct |
8 | Correct | 7 ms | 5624 KB | Output is correct |
9 | Correct | 9 ms | 5624 KB | Output is correct |
10 | Correct | 8 ms | 5624 KB | Output is correct |
11 | Correct | 9 ms | 5624 KB | Output is correct |
12 | Correct | 9 ms | 5488 KB | Output is correct |
13 | Correct | 10 ms | 5624 KB | Output is correct |
14 | Correct | 8 ms | 5496 KB | Output is correct |
15 | Correct | 9 ms | 5368 KB | Output is correct |
16 | Correct | 9 ms | 5496 KB | Output is correct |
17 | Correct | 9 ms | 5496 KB | Output is correct |
18 | Correct | 12 ms | 5368 KB | Output is correct |
19 | Correct | 9 ms | 5496 KB | Output is correct |
20 | Correct | 515 ms | 43628 KB | Output is correct |
21 | Correct | 566 ms | 43328 KB | Output is correct |
22 | Correct | 519 ms | 43552 KB | Output is correct |
23 | Correct | 597 ms | 43256 KB | Output is correct |
24 | Execution timed out | 2073 ms | 214408 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 | 6 ms | 5112 KB | Output is correct |
3 | Correct | 5 ms | 5112 KB | Output is correct |
4 | Correct | 5 ms | 4984 KB | Output is correct |
5 | Correct | 8 ms | 5496 KB | Output is correct |
6 | Correct | 8 ms | 5368 KB | Output is correct |
7 | Correct | 10 ms | 5496 KB | Output is correct |
8 | Correct | 7 ms | 5624 KB | Output is correct |
9 | Correct | 9 ms | 5624 KB | Output is correct |
10 | Correct | 8 ms | 5624 KB | Output is correct |
11 | Correct | 9 ms | 5624 KB | Output is correct |
12 | Correct | 9 ms | 5488 KB | Output is correct |
13 | Correct | 10 ms | 5624 KB | Output is correct |
14 | Correct | 8 ms | 5496 KB | Output is correct |
15 | Correct | 9 ms | 5368 KB | Output is correct |
16 | Correct | 9 ms | 5496 KB | Output is correct |
17 | Correct | 9 ms | 5496 KB | Output is correct |
18 | Correct | 12 ms | 5368 KB | Output is correct |
19 | Correct | 9 ms | 5496 KB | Output is correct |
20 | Correct | 515 ms | 43628 KB | Output is correct |
21 | Correct | 566 ms | 43328 KB | Output is correct |
22 | Correct | 519 ms | 43552 KB | Output is correct |
23 | Correct | 597 ms | 43256 KB | Output is correct |
24 | Execution timed out | 2073 ms | 214408 KB | Time limit exceeded |
25 | Halted | 0 ms | 0 KB | - |