Submission #986986

#TimeUsernameProblemLanguageResultExecution timeMemory
986986activedeltorreLongest Trip (IOI23_longesttrip)C++17
85 / 100
12 ms956 KiB
#include "longesttrip.h" #include <deque> #include <vector> #include <algorithm> using namespace std; int fre[100005]; deque<int>dq1; deque<int>dq2; vector<int>ans1,ans2; vector<int>raspuns; int are_connecte(int a,int b) { vector<int>pl1,pl2; pl1.push_back(a); pl2.push_back(b); return are_connected(pl1,pl2); } void solus(int kuk,int pz2) { int pen,i; vector<int>v1,pl2; int st=0,dr=ans1.size()-1; v1.clear(); v1.push_back(kuk); while(st<=dr) { pl2.clear(); int mij=(st+dr)/2; for(i=0; i<=mij; i++) { pl2.push_back(ans1[i]); } if(are_connected(pl2,v1)==1) { dr=mij-1; } else { st=mij+1; } } pen=dr+1; for(i=pen-1; i>=0; i--) { raspuns.push_back(ans1[i]); } for(i=ans1.size()-1; i>=pen; i--) { raspuns.push_back(ans1[i]); } for(i=pz2; i>=0; i--) { raspuns.push_back(ans2[i]); } for(i=ans2.size()-1; i>pz2; i--) { raspuns.push_back(ans2[i]); } } vector<int> longest_trip(int N, int D) { int i,n=N,capst1,capdr1,capst2,capdr2; ans1.clear(); ans2.clear(); raspuns.clear(); if(are_connecte(0,1)==1) { capst1=0; capdr1=1; dq1.push_front(1); dq1.push_front(0); } else { capst1=0; capdr1=0; capst2=1; capdr2=1; dq2.push_front(1); dq1.push_front(0); } for(i=2; i<n; i++) { if(dq2.size()==0) { capst2=i; capdr2=i; dq2.push_front(i); } else { if(are_connecte(i,capst1)==1) { capst1=i; dq1.push_front(i); } else if(are_connecte(i,capst2)==1) { capst2=i; dq2.push_front(i); } else { capst1=capdr2; while(dq2.size()) { dq1.push_front(dq2.front()); dq2.pop_front(); } capst2=i; capdr2=i; dq2.push_front(i); } } } while(dq1.size()) { ans1.push_back(dq1.front()); dq1.pop_front(); } while(dq2.size()) { ans2.push_back(dq2.front()); dq2.pop_front(); } if(ans2.size()>ans1.size()) { swap(ans1,ans2); } if(are_connected(ans1,ans2)==0) { return ans1; } else { int a,b,c,d; a=ans1[0]; b=ans1.back(); c=ans2[0]; int gay=1; if(are_connecte(a,c)==1 && gay==1) { reverse(ans1.begin(),ans1.end()); for(i=0; i<ans2.size(); i++) { ans1.push_back(ans2[i]); } return ans1; } else if(are_connecte(b,c)==1 && gay==1) { for(i=0; i<ans2.size(); i++) { ans1.push_back(ans2[i]); } return ans1; } else { vector<int>pl2; if(ans2.size()>=2) { d=ans2.back(); if(are_connecte(a,d)) { for(i=0; i<ans1.size(); i++) { ans2.push_back(ans1[i]); } return ans2; } int st=0,dr=ans2.size()-1; while(st<=dr) { pl2.clear(); int mij=(st+dr)/2; for(i=0; i<=mij; i++) { pl2.push_back(ans2[i]); } if(are_connected(pl2,ans1)==1) { dr=mij-1; } else { st=mij+1; } } solus(ans2[dr+1],dr+1); return raspuns; /* for(i=0;i<ans2.size();i++) { pl2.clear(); pl2.push_back(ans2[i]); if(are_connected(pl2,ans1)) { solus(ans2[i],i); return raspuns; } }*/ } else { solus(ans2[0],0); return raspuns; } } } }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |             for(i=0; i<ans2.size(); i++)
      |                      ~^~~~~~~~~~~~
longesttrip.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             for(i=0; i<ans2.size(); i++)
      |                      ~^~~~~~~~~~~~
longesttrip.cpp:166:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                     for(i=0; i<ans1.size(); i++)
      |                              ~^~~~~~~~~~~~
longesttrip.cpp:62:22: warning: variable 'capdr1' set but not used [-Wunused-but-set-variable]
   62 |     int i,n=N,capst1,capdr1,capst2,capdr2;
      |                      ^~~~~~
#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...