Submission #936566

#TimeUsernameProblemLanguageResultExecution timeMemory
936566azberjibiouLongest Trip (IOI23_longesttrip)C++17
100 / 100
11 ms1416 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; const int mxN=300; int N; bool Chk[mxN]; vector <int> makev(int a){ vector <int> tmp; tmp.push_back(a); return tmp; } vector <int> makevlong(vector <int> v, int s, int e){ vector <int> res; for(int i=s;i<=e;i++) res.push_back(v[i]); return res; } vector <int> solv_bipartite(vector <int> v1, vector <int> v2){ if(!are_connected(v1, v2)){ if(v1.size()>v2.size()) swap(v1, v2); return v2; } if(v1.size()>=2 && !are_connected(makev(v1[0]), makev(v1.back()))){ if(are_connected(makev(v1.back()), makev(v2.back()))){ while(v2.size()){ v1.push_back(v2.back()); v2.pop_back(); } return v1; } else{ for(int x : v1) v2.push_back(x); return v2; } } if(v2.size()>=2 && !are_connected(makev(v2[0]), makev(v2.back()))){ if(are_connected(makev(v2.back()), makev(v1.back()))){ while(v2.size()){ v1.push_back(v2.back()); v2.pop_back(); } return v1; } else{ for(int x : v2) v1.push_back(x); return v1; } } int s1=0, e1=(int)v1.size()-1; while(s1!=e1){ int mid=(s1+e1)/2; if(are_connected(makevlong(v1, s1, mid), v2)) e1=mid; else s1=mid+1; } int s2=0, e2=(int)v2.size()-1; while(s2!=e2){ int mid=(s2+e2)/2; if(are_connected(makev(v1[s1]), makevlong(v2, s2, mid))) e2=mid; else s2=mid+1; } vector <int> ans; for(int i=s1+1;i<v1.size();i++) ans.push_back(v1[i]); for(int i=0;i<=s1;i++) ans.push_back(v1[i]); for(int i=s2;i<v2.size();i++) ans.push_back(v2[i]); for(int i=0;i<s2;i++) ans.push_back(v2[i]); return ans; } vector <int> solv1(vector <int> v1); vector <int> solv2(vector <int> v1, vector <int> v2); vector <int> solv2(vector <int> v1, vector <int> v2){ vector <int> nc; for(int i=0;i<N;i++) Chk[i]=false; for(int x : v1) Chk[x]=true; for(int x : v2) Chk[x]=true; for(int i=0;i<N;i++) if(!Chk[i]) nc.push_back(i); if(nc.empty()){ return solv_bipartite(v1, v2); } else if(nc.size()==1){ int p=nc.back(); int l=v1.back(), r=v2.back(); bool res1=are_connected(makev(p), makev(l)), res2=are_connected(makev(p), makev(r)); if(res1 && res2){ v1.push_back(p); while(v2.size()){ v1.push_back(v2.back()); v2.pop_back(); } return v1; } else if(res1){ v1.push_back(p); return solv_bipartite(v1, v2); } else if(res2){ v2.push_back(p); return solv_bipartite(v1, v2); } } else{ int p=nc[0], q=nc[1]; int l=v1.back(), r=v2.back(); bool res1=are_connected(makev(p), makev(l)); if(!res1){ v2.push_back(p); return solv2(v1, v2); } else{ bool res2=are_connected(makev(p), makev(q)), res3=are_connected(makev(q), makev(r)); if(res2 && res3){ v1.push_back(p), v1.push_back(q); while(v2.size()){ v1.push_back(v2.back()); v2.pop_back(); } return solv1(v1); } else if(res2 && !res3){ v1.push_back(p), v1.push_back(q); return solv2(v1, v2); } else if(!res2 && res3){ v1.push_back(p), v2.push_back(q); return solv2(v1, v2); } else{ v1.push_back(q), v2.push_back(p); return solv2(v1, v2); } } } } vector <int> solv1(vector <int> v1){ for(int i=0;i<N;i++) Chk[i]=false; for(int x : v1) Chk[x]=true; for(int i=0;i<N;i++) if(!Chk[i]){ if(are_connected(makev(i), makev(v1.back()))) v1.push_back(i); else{ vector <int> v2; v2.push_back(i); return solv2(v1, v2); } } return v1; } vector<int> longest_trip(int n, int D) { N=n; return solv1(makev(0)); }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> solv_bipartite(std::vector<int>, std::vector<int>)':
longesttrip.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=s1+1;i<v1.size();i++) ans.push_back(v1[i]);
      |                    ~^~~~~~~~~~
longesttrip.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=s2;i<v2.size();i++) ans.push_back(v2[i]);
      |                  ~^~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> solv2(std::vector<int>, std::vector<int>)':
longesttrip.cpp:70:18: warning: control reaches end of non-void function [-Wreturn-type]
   70 |     vector <int> nc;
      |                  ^~
#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...