제출 #421603

#제출 시각아이디문제언어결과실행 시간메모리
421603Sundavar통행료 (IOI18_highway)C++14
12 / 100
3078 ms22548 KiB
#include <bits/stdc++.h> #include "highway.h" using namespace std; typedef pair<int,int> pii; typedef long long ll; struct node{ vector<pii> to; int depth = 0, cnt = 0; bool was = false; }; vector<node> graph; void DFS(int curr){ graph[curr].was = true; for(pii& a : graph[curr].to) if(!graph[a.first].was) graph[a.first].depth = graph[curr].depth +1, DFS(a.first); graph[curr].was = false; } int middle = -1; int cnt(int curr){ graph[curr].was = true; graph[curr].cnt = 1; for(pii& a : graph[curr].to) if(!graph[a.first].was) graph[curr].cnt += cnt(a.first); graph[curr].was = false; return graph[curr].cnt; } int centroid(int curr, int si){ graph[curr].was = true; int mxm = si - graph[curr].cnt, ans = -1; for(pii& a : graph[curr].to) if(!graph[a.first].was){ mxm = max(mxm, graph[a.first].cnt); ans = max(ans, centroid(a.first, si)); } if(mxm <= si/2) ans = curr; graph[curr].was = false; return ans; } void walk(int curr, vector<pii>& v){ graph[curr].was = true; for(pii& a : graph[curr].to) if(!graph[a.first].was){ v.push_back(a); walk(a.first, v); } graph[curr].was = false; } vector<int> lef,rig; int getMiddle(vector<int> v, int at, int A, int B){ if(v.size() <= 2) return v[0]; int cent = centroid(v[0], cnt(v[0])); int si = cnt(cent); int have = 0; vector<pii> v1, v2; graph[cent].was = true; for(pii& a : graph[cent].to){ if(graph[a.first].was) continue; if(have + graph[a.first].cnt <= si/2) have += graph[a.first].cnt, v1.push_back(a), walk(a.first, v1); else v2.push_back(a), walk(a.first, v2); } graph[cent].was = false; vector<int> S(graph.size()-1, 0); for(pii& a : v1) S[a.second] = 1; ll d = ask(S); lef = {cent}, rig = {cent}; for(pii& a : v1) lef.push_back(a.first); for(pii& a : v2) rig.push_back(a.first); if(d == at*A){ for(pii& a : v1) graph[a.first].was = true; return getMiddle(rig, at, A, B); } else if(d == at*B){ for(pii& a : v2) graph[a.first].was = true; return getMiddle(lef, at, A, B); } return cent; } void walk(int curr, vector<int>& s){ graph[curr].was = true; for(pii& a : graph[curr].to) if(!graph[a.first].was) s[a.second] = 1, walk(a.first, s); graph[curr].was = false; } int get(int root, int N, ll at, ll A, ll B, vector<int> v){ for(node& a : graph) a.was = true, a.depth = -1; graph[root].depth = 0; for(int& a : v) graph[a].was = false; DFS(root); vector<int> s(N-1, 0); walk(root, s); ll d = ask(s), depth = (d-at*A)/(B-A); if(depth == 0) return root; vector<pii> poss; for(int i = 0; i < N; i++) if(graph[i].depth == depth-1) for(pii& a : graph[i].to) if(graph[a.first].depth == depth) poss.push_back(a); while(poss.size() > 1){ s.assign(N-1, 0); for(int i = 0; i < poss.size()/2; i++) s[poss[i].second] = 1; if(ask(s) == (at-1)*A + B) poss.resize(poss.size()/2); else{ vector<pii> uj; for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]); poss = uj; } } return poss[0].first; } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { graph.resize(N); int M = U.size(); for(int i = 0; i < M; i++){ graph[U[i]].to.push_back({V[i],i}); graph[V[i]].to.push_back({U[i],i}); } vector<int> v(N); for(int i = 0; i < N; i++) v[i] = i; vector<int> s(M, 0); ll at = ask(s)/A; int middle = getMiddle(v, at, A, B); int S = get(middle, N, at, A, B, lef); int T = get(middle, N, at, A, B, rig); answer(S, T); }

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

highway.cpp: In function 'int get(int, int, ll, ll, ll, std::vector<int>)':
highway.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0; i < poss.size()/2; i++) s[poss[i].second] = 1;
      |                    ~~^~~~~~~~~~~~~~~
highway.cpp:113:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |       for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
      |                                  ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...