제출 #746144

#제출 시각아이디문제언어결과실행 시간메모리
746144almothana05통행료 (IOI18_highway)C++14
0 / 100
3064 ms8528 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; vector<pair<int , int> >kinder[300000] , ka; vector<int>cent , ed; int sub[300000], vis[300000]; long long a , b , menge , cmp , comp ,numm , kind , vase; int st , en , mid , mit; int centroid(int x , int f , int n){ for(int i = 0 ; i < kinder[x].size() ; i++){ kind = kinder[x][i].first; if(vis[kind] != 2 &&kind != f && sub[kind] * 2 > n){ return centroid(kind , x , n); } } for(int i = 0 ; i < kinder[x].size() ; i++){ ed[kinder[x][i].second] = 1; } vis[x] = 2; return x; } int dfs(int x){ vis[x] = 1; sub[x] = 1; for(int i = 0 ; i < kinder[x].size() ; i++){ kind = kinder[x][i].first; if(vis[kind] == 0){ sub[x] += dfs(kind); } } return sub[x]; } int bis(int x , int y , long long z ,int f , int root){ for(int i = 0 ; i <= y ; i++){ ed[kinder[root][i].second] = 1; } st = x ; en = y; mid = y; while(st <= en){ mit = (st + en)/2; while(mid > mit){ if(kinder[root][mid].first == f || vis[kinder[root][mid].first] == 2){ mid--; continue; } ed[kinder[root][mid].second] = 0; mid--; } while(mid <= mit){ if(kinder[root][mid].first == f || vis[kinder[root][mid].first] == 2){ mid++; continue; } ed[kinder[root][mid].second] = 1; mid++; } if(mid > mit){ mid--; } numm = ask(ed); if(numm >= z){ en = mit - 1; } else{ st = mit + 1; } } for(int i = 0 ; i <= y ; i++){ ed[kinder[root][i].second] = 1; } return st; } long long suche(int x){ // cout << x << "\n"; dfs(x); long long nummer = centroid(x ,x , sub[x]); // cout << nummer << ' ' << x << "\n"; // cout << kinder[nummer].size() << "\n"; int fater = -1,pl; for(int i = 0 ; i < kinder[nummer].size() ; i++ ){ if(sub[kinder[nummer][i].first] > sub[nummer] && vis[kinder[nummer][i].first] != 2){ fater = kinder[nummer][i].first; break; } } // cout << fater << "\n"; cmp = ask(ed); // cout << cmp - comp << "\n"; if(nummer == x){ while(true); if(cmp == comp){ return nummer; } else{ comp = cmp; pl = bis(0 , kinder[nummer].size() - 1 , cmp , fater , nummer ); } } else{ if(cmp == comp){ // while(true); return suche(x); } else if(cmp == comp + b - a){ comp = cmp; // while(true); return nummer; } else{ while(true); comp = cmp; pl = bis(0 , kinder[nummer].size() - 1 , cmp , fater , nummer ); // cout << kinder[nummer].size() << "\n"; } } return suche(kinder[nummer][pl].first); } void finde(){ cent.clear(); ka.clear(); for(int i = 0 ; i < menge ; i++){ if(vis[i] == 0){ ka.push_back({i , dfs(i)}); } } for(int i = 0 ; i < ka.size() ; i++){ cent.push_back(centroid(ka[i].first , ka[i].first , ka[i].second)); // cout << cent[i] << ' '; } // cout << "\n"; for(int i = 0 ; i < menge ; i++){ if(vis[i] == 1){ vis[i] = 0; } } ka.clear(); comp = ask(ed); vase = comp; if(comp > cmp){ st = 0 ; en = cent.size() - 2; mid = cent.size() - 1; while(st <= en){ mit = (st + en)/2; while(mid > mit){ for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){ ed[kinder[cent[mid]][i].second] = 0; } mid--; } while(mid <= mit){ for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){ ed[kinder[cent[mid]][i].second] = 1; } mid++; } if(mid > mit){ mid--; } numm = ask(ed); if(numm == comp){ en = mit - 1; } else{ st = mit + 1; } } int root , er ,zw; root = cent[st]; // cout << root << "\n"; cent.clear(); er = bis(0 , kinder[root].size() - 1 , cmp +b -a , -1 , root); // cout << er << "\n"; if(comp == cmp + b - a){ er = suche(kinder[root][er].first); zw = root; } else{ er = suche(kinder[root][er].first); while(true); zw = bis(er , kinder[root].size() - 1 , comp , -1 , root); // cout << zw << ' ' << kinder[root][zw].first << "\n"; // cout << kinder[root][er].first << "\n"; zw = suche(kinder[root][zw].first); // cout << zw << "\n"; } // comp = ask(ed); // cout << er << "\n"; answer(er , zw); return; } cent.clear(); finde(); } void find_pair(int N, vector<int> u, vector<int> v, int A, int B) { a = A; b = B; menge = N; for(int i = 0 ; i < u.size() ; i++){ kinder[u[i]].push_back({v[i] , i}); kinder[v[i]].push_back({u[i] , i}); ed.push_back(0); } cmp = ask(ed); finde(); }

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

highway.cpp: In function 'int centroid(int, int, int)':
highway.cpp:10:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   for(int i = 0 ; i < kinder[x].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
highway.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int i = 0 ; i < kinder[x].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'int dfs(int)':
highway.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i = 0 ; i < kinder[x].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'long long int suche(int)':
highway.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i = 0 ; i < kinder[nummer].size() ; i++ ){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void finde()':
highway.cpp:135:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for(int i = 0 ; i < ka.size() ; i++){
      |                   ~~^~~~~~~~~~~
highway.cpp:154:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |           for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
      |                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:162:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |           for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
      |                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:212:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |   for(int i = 0 ; i < u.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...