Submission #1067827

#TimeUsernameProblemLanguageResultExecution timeMemory
1067827kunzaZa183Torrent (COI16_torrent)C++17
31 / 100
692 ms27220 KiB
#include <bits/stdc++.h> using namespace std; int main(){ int n,st,ed; cin>>n>>st>>ed; st--,ed--; vector<vector<int>> adj(n); for(int i =0; i < n-1;i++) { int x,y; cin>>x>>y; x--,y--; adj[x].push_back(y),adj[y].push_back(x); } vector<int> bet(n); vector<int> path; function<void(int,int)> fp = [&](int cur,int par) { path.push_back(cur); if(cur==ed){ return; } for(auto a:adj[cur]) if(a!=par) { fp(a,cur); if(path.back()==ed) return; } path.pop_back(); }; fp(st,st); for(auto a:path) bet[a] = 1; auto valv = [&](vector<int> & vi) { if(vi.empty()) return 0; sort(vi.begin(),vi.end(),greater<int>()); for(int i = 0; i < vi.size();i++) vi[i] += i+1; return *max_element(vi.begin(),vi.end()); }; function<int(int,int)> outdp = [&](int cur,int par) { vector<int> vi; for(auto a:adj[cur]) if(a != par && bet[a] == 0) vi.push_back(outdp(a, cur)); return valv(vi); }; vector<int> dp(n); for(int i = 1; i < ((int) path.size()) - 1; i++) dp[path[i]] = outdp(path[i],path[i]); multiset<int> sst,sed; for(auto a:adj[st]) if(bet[a] == 0) { sst.insert(outdp(a,a)); } for(auto a:adj[ed]) if(bet[a] == 0) { sed.insert(outdp(a,a)); } int minans = n; multiset<int> vi,vi2; auto val = [](multiset<int> &msi) { if(msi.empty()) return 0; return int(msi.size()) + *msi.begin(); }; vector<int> pcomp1(path.size()),pcomp2(path.size()); multiset<int> idk1,idk2; for(int i = 1; i < path.size() - 1;i++){ if(i>1) { idk1.erase(idk1.find(dp[path[i-1]] + i - 2)); idk1.insert(dp[path[i-1]] + i - 1); } if(i>0) idk1.insert(dp[path[i]] + i - 1); pcomp1[i] = *idk1.rbegin(); } reverse(path.begin(),path.end()); for(int i = 1; i < path.size() - 1;i++){ if(i>1) { idk2.erase(idk2.find(dp[path[i-1]] + i - 2)); idk2.insert(dp[path[i-1]] + i - 1); } if(i>0) idk2.insert(dp[path[i]] + i - 1); pcomp2[i] = *idk2.rbegin(); } reverse(pcomp2.begin(),pcomp2.end()); // for(auto a:pcomp1) // cout<<a<<' '; // cout<<"\n"; // for(auto a:pcomp2) // cout<<a<<' '; // cout<<'\n'; reverse(path.begin(),path.end()); // for(auto a:path) // cout<<dp[a]<<" "; // cout<<"\n"; for(int i = 0; i < path.size() - 1;i++) { vector<int> vi1,vi2; for(auto a:sst) vi1.push_back(a); for(auto a:sed) vi2.push_back(a); if(i!=0) vi1.push_back(pcomp1[i]); if(i!=path.size() - 2) vi2.push_back(pcomp2[i + 1]); // for(auto a:vi1) // cout<<a<<" "; // cout<<"\n"; // for(auto a:vi2) // cout<<a<<" "; // cout<<"\n\n"; minans = min(minans,max(valv(vi1), valv(vi2))); } cout<<minans<<"\n"; }

Compilation message (stderr)

torrent.cpp: In lambda function:
torrent.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < vi.size();i++)
      |                    ~~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i = 1; i < path.size() - 1;i++){
      |                  ~~^~~~~~~~~~~~~~~~~
torrent.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int i = 1; i < path.size() - 1;i++){
      |                  ~~^~~~~~~~~~~~~~~~~
torrent.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int i = 0; i < path.size() - 1;i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
torrent.cpp:124:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     if(i!=path.size() - 2)
      |        ~^~~~~~~~~~~~~~~~~
torrent.cpp:73:8: warning: variable 'val' set but not used [-Wunused-but-set-variable]
   73 |   auto val = [](multiset<int> &msi) {
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...