제출 #895211

#제출 시각아이디문제언어결과실행 시간메모리
895211anton열대 식물원 (Tropical Garden) (IOI11_garden)C++17
0 / 100
1 ms4444 KiB
#include "garden.h" #include "gardenlib.h" #include<bits/stdc++.h> using namespace std; #define pii pair<int, int> const int INF = 1e9+1; const int MAX_N = 2*1e5; int bl[2*MAX_N][30]; int max_p[MAX_N]; vector<vector<pii>> adj; int target; int n; int dfs(int u, vector<int>& vis, int d){ //cout<<"dfs "<<u<<" "<<u%n<<" "<<u/n<<endl; vis[u] =d; if(vis[bl[u][0]] == -1){ return dfs(bl[u][0], vis, d+1); } else{ if(bl[u][0] == target){ return d+1; } else{ return -1; } } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { n =N; adj.resize(N); for(int i = 0; i <M; i++){ adj[R[i][0]].push_back(pii(i, R[i][1])); adj[R[i][1]].push_back(pii(i, R[i][0])); } for(int i = 0; i<N; i++){ max_p[i] = adj[i][0].first; } for(int i = 0; i<N; i++){ bl[i][0] = adj[i][0].second; if(adj[i][0].first == max_p[adj[i][0].second]){ bl[i][0] += N; } if(adj[i].size()>1){ bl[i+N][0] = adj[i][1].second; if(adj[i][1].first == max_p[adj[i][1].second]){ bl[i+N][0] += N; } } else{ bl[i+N][0] = bl[i][0]; } } for(int step = 1; step<30; step++){ for(int i = 0; i<2*N; i++){ bl[i][step] = bl[bl[i][step-1]][step-1]; } } vector<int> res(Q); auto calc = [&](){ vector<int> ch(2*N, -1); int len = dfs(target, ch, 0); for(auto e:ch){ //cout<<e<<" "; } //cout<<endl; //cout<<len<<endl; if(len == -1){ map<int, int> oc; for(int i = 0; i<N; i++){ if(adj[i%N].size()>1 || i<N){ int dist= -1; if(i == target){ dist = 0; } else if(ch[i]!=-1){ dist= -1; } else{ int cur = i; dist = 1; for(int step = 29; step>=0; step--){ if(ch[bl[cur][step]] == -1){ cur = bl[cur][step]; dist+= (1<<step); } } if(bl[cur][0] == target){ } else{ dist = -1; } } //cout<<i<<"dist "<<dist<<endl; if(dist!=-1){ oc[dist] ++; } } } for(int i = 0; i<Q; i++){ if(G[i]<2*N){ res[i] += oc[G[i]]; } } } else{ vector<vector<int>> oc(len); for(int i = 0; i<N; i++){ if(adj[i%N].size()>1 || i<N){ int dist= -1; if(i == target){ dist = 0; } else if(ch[i]!=-1){ dist= len-ch[i]; } else{ int cur = i; dist = 1; for(int step = 29; step>=0; step--){ if(ch[bl[cur][step]] == -1){ cur = bl[cur][step]; dist++; } } if(ch[bl[cur][0]] != -1){ dist += len-ch[bl[cur][0]]; } else{ dist = -1; } } //cout<<i<<"dist "<<dist<<endl; if(dist!=-1){ oc[dist%len].push_back(dist); } } } for(auto e: oc){ sort(e.begin(), e.end()); } for(int i = 0; i<Q; i++){ int mod = G[i]%len; int cur =-1; for(int step = (1<<29); step>0; step/=2){ if(cur+step< oc[mod].size() && oc[mod][cur+step]<=G[i]){ cur+=step; } } res[i]+=cur+1; } } }; target = P; calc(); target = P+N; calc(); for(auto e: res){ answer(e); } }

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In lambda function:
garden.cpp:74:14: warning: unused variable 'e' [-Wunused-variable]
   74 |     for(auto e:ch){
      |              ^
garden.cpp:166:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                 if(cur+step< oc[mod].size() && oc[mod][cur+step]<=G[i]){
      |                    ~~~~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...