제출 #429399

#제출 시각아이디문제언어결과실행 시간메모리
429399peuch통행료 (IOI18_highway)C++17
11 / 100
440 ms262148 KiB
#include "highway.h" #include<bits/stdc++.h> using namespace std; int n; vector<vector<int> > ar, id; vector<int> marc, sub, pai; vector<int> nulo; vector<int> ans; long long iniVal; void centDecomp(int cur, bool flag, int p); void preCalc(int cur, int p); void preCalc2(int cur, int p); int getCent(int cur, int pai, int tam); void paint(int cur, int pai, vector<int>& w); int bb(vector<int> values); pair<int, int> bb2(vector<int> values); bool query(vector<int> w); void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { n = N; ar = id = vector<vector<int> > (n); marc = sub = pai = vector<int> (n); nulo = vector<int> (U.size()); for(int i = 0; i < U.size(); i++){ ar[U[i]].push_back(V[i]); ar[V[i]].push_back(U[i]); id[U[i]].push_back(i); id[V[i]].push_back(i); } iniVal = ask(nulo); centDecomp(0, 1, 0); sort(ans.begin(), ans.end()); // printf("%d %d %d\n", ans.size(), ans[0], ans[1]); answer(ans[0], ans[1]); } void centDecomp(int cur, bool flag, int p){ // printf("%d %d %d\n", cur, flag, p); if(marc[cur]){ ans.push_back(cur); return; } preCalc(cur, cur); int cent = getCent(cur, cur, sub[cur]); // printf("Cent: %d Flag: %d\n", cent, flag); marc[cent] = 1; vector<int> w = nulo; vector<int> filhos; for(int i = 0; i < ar[cent].size(); i++){ if(!flag && ar[cent][i] == pai[cent]) continue; if(marc[ar[cent][i]]) continue; filhos.push_back(ar[cent][i]); w[id[cent][i]] = 1; } if(filhos.empty()){ vector<int> w = nulo; for(int i = 0; i < ar[cent].size(); i++) w[id[cent][i]] = 1; if(query(w)) ans.push_back(cent); else centDecomp(pai[cent], 0, cent); return; } if(flag && query(w)){ pair<int, int> val = bb2(filhos); int n1 = val.first; int n2 = val.second; preCalc2(cent, cent); if(n1 != -1) centDecomp(n1, 0, cent); if(n2 != -1) centDecomp(n2, 0, cent); if(n2 == -1 || n1 == -1) ans.push_back(cent); return; } if(!flag){ int next = bb(filhos); if(next == -1){ vector<int> w = nulo; for(int i = 0; i < ar[cent].size(); i++) w[id[cent][i]] = 1; if(query(w)) ans.push_back(cent); else centDecomp(pai[cent], 0, cent); } else centDecomp(next, 0, cent); return; } int next = bb(filhos); centDecomp(next, 1, cent); } void preCalc(int cur, int p){ sub[cur] = 1; for(int i = 0; i < ar[cur].size(); i++){ int viz = ar[cur][i]; if(marc[viz] || viz == p) continue; preCalc(viz, cur); sub[cur] += sub[viz]; } } void preCalc2(int cur, int p){ sub[cur] = 1; for(int i = 0; i < ar[cur].size(); i++){ int viz = ar[cur][i]; if(marc[viz] || viz == p) continue; preCalc2(viz, cur); pai[viz] = cur; } } int getCent(int cur, int pai, int tam){ for(int i = 0; i < ar[cur].size(); i++){ int viz = ar[cur][i]; if(marc[viz] || viz == pai || sub[viz] <= tam / 2) continue; return getCent(viz, cur, tam); } return cur; } void paint(int cur, int pai, vector<int>& w){ for(int i = 0; i < ar[cur].size(); i++){ int viz = ar[cur][i]; w[id[cur][i]] = 1; if(marc[viz] || viz == pai) continue; paint(viz, cur, w); } } int bb(vector<int> values){ int ini = 0, fim = values.size() - 1; vector<int> w = nulo; for(int i = 0; i < values.size(); i++) paint(values[i], values[i], w); if(!query(w)) return -1; while(ini != fim){ int mid = (ini + fim) >> 1; vector<int> w = nulo; for(int i = ini; i <= mid; i++) paint(values[i], values[i], w); if(query(w)) fim = mid; else ini = mid + 1; } return values[ini]; } pair<int, int> bb2(vector<int> values){ int ini = 0, fim = values.size() - 1; vector<int> w = nulo; for(int i = 0; i < values.size(); i++) paint(values[i], values[i], w); long long val = ask(w); if(val == iniVal) return make_pair(-1, -1); while(ini != fim){ int mid = (ini + fim) >> 1; vector<int> w = nulo; for(int i = ini; i <= mid; i++) paint(values[i], values[i], w); long long auxVal = ask(w); if(auxVal == val) fim = mid; else if(auxVal == iniVal) ini = mid + 1; else{ vector<int> v1, v2; for(int i = 0; i <= mid; i++) v1.push_back(values[i]); for(int i = mid + 1; i <= fim; i++) v2.push_back(values[i]); return make_pair(bb(v1), bb(v2)); } } return make_pair(values[ini], -1); } bool query(vector<int> w){ return ask(w) != iniVal; }

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

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < U.size(); i++){
      |                 ~~^~~~~~~~~~
highway.cpp: In function 'void centDecomp(int, bool, int)':
highway.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < ar[cent].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
highway.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i = 0; i < ar[cent].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
highway.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for(int i = 0; i < ar[cent].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void preCalc(int, int)':
highway.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void preCalc2(int, int)':
highway.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
highway.cpp: In function 'int getCent(int, int, int)':
highway.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void paint(int, int, std::vector<int>&)':
highway.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
highway.cpp: In function 'int bb(std::vector<int>)':
highway.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for(int i = 0; i < values.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'std::pair<int, int> bb2(std::vector<int>)':
highway.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |  for(int i = 0; i < values.size(); 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...