# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
68653 | 2018-08-17T19:06:37 Z | TadijaSebez | Bitaro’s Party (JOI18_bitaro) | C++11 | 2000 ms | 202956 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back const int N=100050; const int inf=1e9+7; const int S=50; vector<int> E[N]; vector<pair<int,int> > dp[N]; set<pair<int,int> > pq; map<int,int> dist[N]; bool was[N]; int tmp[N]; int main() { int n,m,q,i,j,u,v,k; scanf("%i %i %i",&n,&m,&q); for(i=1;i<=m;i++) scanf("%i %i",&u,&v),E[v].pb(u); for(i=1;i<=n;i++) { pq.insert(mp(0,i)); for(j=0;j<E[i].size();j++) { v=E[i][j]; for(k=0;k<dp[v].size();k++) { int h=dp[v][k].second; if(dist[i].count(h) && pq.count(mp(dist[i][h],h))) { if(dist[i][h]<dp[v][k].first+1) { pq.erase(mp(dist[i][h],h)); dist[i][h]=dp[v][k].first+1; pq.insert(mp(dist[i][h],h)); } } else pq.insert(mp(dp[v][k].first+1,dp[v][k].second)),dist[i][h]=dp[v][k].first+1; if(pq.size()>=S) pq.erase(pq.begin()); } } while(pq.size()) dp[i].pb(*pq.begin()),pq.erase(pq.begin()); } while(q--) { int sz,st; vector<int> x; scanf("%i %i",&st,&sz); x.resize(sz); for(i=0;i<sz;i++) scanf("%i",&x[i]),was[x[i]]=1; if(sz>=S) { for(i=1;i<=st;i++) { if(was[i]) tmp[i]=-inf; else tmp[i]=0; for(j=0;j<E[i].size();j++) tmp[i]=max(tmp[i],tmp[E[i][j]]+1); } if(tmp[st]>=0) printf("%i\n",tmp[st]); else printf("-1\n"); } else { int ans=-1; for(i=0;i<dp[st].size();i++) if(!was[dp[st][i].second]) ans=dp[st][i].first; printf("%i\n",ans); } for(i=0;i<sz;i++) was[x[i]]=0; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 11 ms | 9844 KB | Output is correct |
3 | Correct | 10 ms | 9844 KB | Output is correct |
4 | Correct | 11 ms | 9844 KB | Output is correct |
5 | Correct | 29 ms | 11632 KB | Output is correct |
6 | Correct | 33 ms | 11876 KB | Output is correct |
7 | Correct | 30 ms | 11876 KB | Output is correct |
8 | Correct | 21 ms | 12708 KB | Output is correct |
9 | Correct | 25 ms | 12708 KB | Output is correct |
10 | Correct | 25 ms | 12904 KB | Output is correct |
11 | Correct | 26 ms | 12904 KB | Output is correct |
12 | Correct | 34 ms | 12904 KB | Output is correct |
13 | Correct | 26 ms | 12904 KB | Output is correct |
14 | Correct | 28 ms | 12904 KB | Output is correct |
15 | Correct | 28 ms | 12904 KB | Output is correct |
16 | Correct | 28 ms | 12904 KB | Output is correct |
17 | Correct | 32 ms | 12904 KB | Output is correct |
18 | Correct | 30 ms | 12904 KB | Output is correct |
19 | Correct | 33 ms | 12904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 11 ms | 9844 KB | Output is correct |
3 | Correct | 10 ms | 9844 KB | Output is correct |
4 | Correct | 11 ms | 9844 KB | Output is correct |
5 | Correct | 29 ms | 11632 KB | Output is correct |
6 | Correct | 33 ms | 11876 KB | Output is correct |
7 | Correct | 30 ms | 11876 KB | Output is correct |
8 | Correct | 21 ms | 12708 KB | Output is correct |
9 | Correct | 25 ms | 12708 KB | Output is correct |
10 | Correct | 25 ms | 12904 KB | Output is correct |
11 | Correct | 26 ms | 12904 KB | Output is correct |
12 | Correct | 34 ms | 12904 KB | Output is correct |
13 | Correct | 26 ms | 12904 KB | Output is correct |
14 | Correct | 28 ms | 12904 KB | Output is correct |
15 | Correct | 28 ms | 12904 KB | Output is correct |
16 | Correct | 28 ms | 12904 KB | Output is correct |
17 | Correct | 32 ms | 12904 KB | Output is correct |
18 | Correct | 30 ms | 12904 KB | Output is correct |
19 | Correct | 33 ms | 12904 KB | Output is correct |
20 | Correct | 537 ms | 13888 KB | Output is correct |
21 | Correct | 403 ms | 13892 KB | Output is correct |
22 | Correct | 546 ms | 13892 KB | Output is correct |
23 | Correct | 551 ms | 13976 KB | Output is correct |
24 | Execution timed out | 2055 ms | 202956 KB | Time limit exceeded |
25 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 11 ms | 9844 KB | Output is correct |
3 | Correct | 10 ms | 9844 KB | Output is correct |
4 | Correct | 11 ms | 9844 KB | Output is correct |
5 | Correct | 29 ms | 11632 KB | Output is correct |
6 | Correct | 33 ms | 11876 KB | Output is correct |
7 | Correct | 30 ms | 11876 KB | Output is correct |
8 | Correct | 21 ms | 12708 KB | Output is correct |
9 | Correct | 25 ms | 12708 KB | Output is correct |
10 | Correct | 25 ms | 12904 KB | Output is correct |
11 | Correct | 26 ms | 12904 KB | Output is correct |
12 | Correct | 34 ms | 12904 KB | Output is correct |
13 | Correct | 26 ms | 12904 KB | Output is correct |
14 | Correct | 28 ms | 12904 KB | Output is correct |
15 | Correct | 28 ms | 12904 KB | Output is correct |
16 | Correct | 28 ms | 12904 KB | Output is correct |
17 | Correct | 32 ms | 12904 KB | Output is correct |
18 | Correct | 30 ms | 12904 KB | Output is correct |
19 | Correct | 33 ms | 12904 KB | Output is correct |
20 | Correct | 537 ms | 13888 KB | Output is correct |
21 | Correct | 403 ms | 13892 KB | Output is correct |
22 | Correct | 546 ms | 13892 KB | Output is correct |
23 | Correct | 551 ms | 13976 KB | Output is correct |
24 | Execution timed out | 2055 ms | 202956 KB | Time limit exceeded |
25 | Halted | 0 ms | 0 KB | - |