제출 #743344

#제출 시각아이디문제언어결과실행 시간메모리
743344drkarlicio2107Torrent (COI16_torrent)C++14
0 / 100
160 ms24804 KiB
#include <bits/stdc++.h> using namespace std; int n, a, b; vector < int > g [200010]; int l [200010]; int dp [200010]; vector <int> pom; int mark_path (int x, int par){ if (x==a) return l [x]=0; int ret=-1; for (int i=0; i<g [x].size(); i++){ int y=g [x][i]; if (y==par) continue; int val=mark_path (y, x); if (val!=-1) ret=val+1; } return l [x]=ret; } int rek (int x, int mid, int par, int od, int sus){ vector <int> my; my.clear (); for (int i=0; i<g [x].size(); i++){ int y=g [x][i]; if (y==par) continue; if (sus && l [y]!=-1) continue; if (l [y]==mid){ if (od && dp [y]==-1) my.push_back (rek (y, mid, x, od, 1)); continue; } if (l [x]==mid){ if (l [y]==mid+1 || (l [y]==mid-1 && mid-1!=-1)){ continue; } } my.push_back (rek (y, mid, x, od, sus)); } sort (my.begin(), my.end()); reverse (my.begin(), my.end()); int sol=0; for (int i=0; i<my.size(); i++) sol=max (sol, my [i]+(i+1)); return dp [x]=sol; } int main(){ memset (l, -1, sizeof l); cin >> n >> a >> b; for (int i=0; i<n-1; i++){ int x, y; cin >> x >> y; g [x].push_back (y); g [y].push_back (x); } mark_path (b, -1); /*cout << "Prosao: " << endl; for (int i=1; i<n+1; i++) cout << l [i] << " "; cout << endl;*/ int lo=0; int hi=l [b]; while (lo!=hi){ int mid=(lo+hi)/2; memset (dp, -1, sizeof dp); int sol1=rek (a, mid, -1, 0, 0); int sol2=rek (b, mid, -1, 1, 0); memset (dp, -1, sizeof dp); int sol3=rek (a, mid+1, -1, 0, 0); int sol4=rek (b, mid+1, -1, 1, 0); if (max (sol1, sol2)==max (sol3, sol4)){ lo=mid; break; } if (max (sol1, sol2)<max (sol3, sol4)) hi=mid; else lo=mid+1; //cout << lo << " " << hi << endl; } memset (dp, -1, sizeof dp); int sol1=rek (a, lo, -1, 0, 0); int sol2=rek (b, lo, -1, 1, 0); //cout << lo << " " << sol1 << " " << sol2 << endl; cout << max (sol1, sol2) << endl; }

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

torrent.cpp: In function 'int mark_path(int, int)':
torrent.cpp:11:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (int i=0; i<g [x].size(); i++){
      |                ~^~~~~~~~~~~~~
torrent.cpp: In function 'int rek(int, int, int, int, int)':
torrent.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i=0; i<g [x].size(); i++){
      |                ~^~~~~~~~~~~~~
torrent.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i=0; i<my.size(); i++) sol=max (sol, my [i]+(i+1));
      |                ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...