Submission #263473

#TimeUsernameProblemLanguageResultExecution timeMemory
263473uacoder123Tropical Garden (IOI11_garden)C++14
69 / 100
5061 ms41080 KiB
#include <bits/stdc++.h> using namespace std; #include "garden.h" #include "gardenlib.h" #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) lli(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; // #define MAX_M 1000000 // #define MAX_Q 2000 // static int N, M, P, Q; // static int R[MAX_M][2]; // static int G[MAX_Q]; // static int solutions[MAX_Q]; // static int answers[MAX_Q]; // static int answer_count; // inline // void my_assert(int e) {if (!e) abort();} // void read_input() // { // int i; // my_assert(3==scanf("%d %d %d",&N,&M,&P)); // for(i=0; i<M; i++) // my_assert(2==scanf("%d %d",&R[i][0],&R[i][1])); // my_assert(1==scanf("%d",&Q)); // for(i=0; i<Q; i++) // my_assert(1==scanf("%d",&G[i])); // for(i=0; i<Q; i++) // my_assert(1==scanf("%d",&solutions[i])); // } // void answer(int x) // { // if(answer_count>=Q) { // printf("Incorrect. Too many answers.\n"); // exit(0); // } // answers[answer_count] = x; // answer_count++; // } lli n,m,d,g; lli ed[300001][2],lim=2000000000,cur,ch=0,co=0,arr[2001],nex[300001],vis[300001],v2[300001]; vi al[300001]; vector<iii> pos[300001],v,v1; lli lev[300001],ya=0; bool cmp(lli a,lli b) { return (a%m)<(b%m); } void dfs1(lli node,int l) { lev[node]=l; vis[node]=1; if(!vis[nex[node]]) dfs1(nex[node],l+1); else { if(v2[nex[node]]==-2) { cur=nex[node]; co=0; while(1) { v2[cur]=3; if(ed[cur][0]==d) { v1.pb(mp(cur,mp(0,0))); } co++; if(cur==node) break; cur=nex[cur]; } for(int i=0;i<v1.size();++i) v.pb(mp(v1[i].F,mp(v1[i].S.F,co))); } else { v2[node]=max(1,v2[node]); ya=lev[nex[node]]-1; for(int i=0;i<pos[nex[node]].size();++i) v.pb(pos[nex[node]][i]); } } if(ya!=-lim) { lev[node]=ya; ya--; } v2[node]=max(1,v2[node]); if(v2[node]!=3&&ed[node][0]==d) v.pb(mp(node,mp((((ed[node][0]==d)?0:1)),lim))); for(int i=0;i<v.size();++i) pos[node].pb(v[i]); } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { n=N; m=M; d=P; for(lli i=0;i<m;++i) { ed[i][0]=R[i][0]; ed[i][1]=R[i][1]; ed[i+m][0]=R[i][1]; ed[i+m][1]=R[i][0]; al[R[i][0]].pb(i); al[R[i][1]].pb(i+m); } for(lli i=0;i<n;++i) sort(all(al[i]),cmp); g=Q; for(lli i=0;i<g;++i) arr[i]=G[i]; for(lli i=0;i<2*m;++i) { v2[i]=-2; if(al[ed[i][1]].size()==1) nex[i]=al[ed[i][1]][0]; else if((al[ed[i][1]][0]%m)!=(i%m)) nex[i]=al[ed[i][1]][0]; else nex[i]=al[ed[i][1]][1]; } memset(vis,0,sizeof(vis)); for(lli i=0;i<n;++i) if(!vis[al[i][0]]) { v.clear(); v1.clear(); ya=-lim; dfs1(al[i][0],0); } for(lli i=0;i<g;++i) { co=0; for(lli j=0;j<n;++j) { for(int k=0;k<pos[al[j][0]].size();++k) { if(pos[al[j][0]].size()>8) exit(1); if(v2[al[j][0]]!=3||lev[al[j][0]]<=lev[pos[al[j][0]][k].F]) { if(arr[i]>=(lev[pos[al[j][0]][k].F]-lev[al[j][0]]+pos[al[j][0]][k].S.F)&&(arr[i]-(lev[pos[al[j][0]][k].F]-lev[al[j][0]]+pos[al[j][0]][k].S.F))%pos[al[j][0]][k].S.S==0) { co++; break; } } else { if(arr[i]>=(pos[al[j][0]][k].S.F+pos[al[j][0]][k].S.S-(lev[al[j][0]]-lev[pos[al[j][0]][k].F]))&&(arr[i]-(pos[al[j][0]][k].S.F+pos[al[j][0]][k].S.S-(lev[al[j][0]]-lev[pos[al[j][0]][k].F])))%pos[al[j][0]][k].S.S==0) { co++; break; } } } } answer(co); } } // int main() // { // int correct, i; // read_input(); // answer_count = 0; // count_routes(N,M,P,R,Q,G); // if(answer_count!=Q) { // printf("Incorrect. Too few answers.\n"); // exit(0); // } // correct = 1; // for(i=0; i<Q; i++) // if(answers[i]!=solutions[i]) // correct = 0; // if(correct) // printf("Correct.\n"); // else { // printf("Incorrect.\n"); // printf("Expected: "); // for(i=0; i<Q; i++) // printf("%d ",solutions[i]); // printf("\nReturned: "); // for(i=0; i<Q; i++) // printf("%d ",answers[i]); // } // return 0; // }

Compilation message (stderr)

garden.cpp: In function 'void dfs1(lli, int)':
garden.cpp:87:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |               for(int i=0;i<v1.size();++i)
      |                           ~^~~~~~~~~~
garden.cpp:94:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |               for(int i=0;i<pos[nex[node]].size();++i)
      |                           ~^~~~~~~~~~~~~~~~~~~~~~
garden.cpp:106:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |           for(int i=0;i<v.size();++i)
      |                       ~^~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:152:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |               for(int k=0;k<pos[al[j][0]].size();++k)
      |                           ~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...