Submission #1061148

#TimeUsernameProblemLanguageResultExecution timeMemory
1061148mychecksedadLongest Trip (IOI23_longesttrip)C++17
100 / 100
11 ms856 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define ll long long #define ff first #define ss second #define vi vector<int> const int N = 200005; vector<vector<int>> is; bool get(int x, int y){ if(is[x][y]) return is[x][y] - 1; for(int j = 0; j < int(is.size()); ++j){ if(j == x || j == y) continue; if(is[j][x] == 1 && is[j][y] == 1){ is[x][y] = is[y][x] = 2; return 2; } } is[x][y] = is[y][x] = are_connected(vi{x}, vi{y}) + 1; return is[x][y] - 1; } std::vector<int> longest_trip(int n, int D) { is.clear(); is.resize(n, vector<int>(n)); if(D == 3){ vector<int> v; for(int i = 0; i < n; ++i) v.pb(i); return v; } if(D == 2){ deque<int> v; v.pb(0); int o = -1; for(int i = 1; i < n; ++i){ bool x = are_connected(vi{0}, vi{i}); if(x){ o = i; v.pb(i); break; } } if(o == -1){ vi res; for(int i = 1; i < n; ++i){ res.pb(i); } return res; } for(int i = 1; i < n; ++i){ if(o == i) continue; bool x = are_connected(vi{v[0]}, vi{i}); if(x){ v.push_front(i); }else v.pb(i); } vector<int> res(all(v)); return res; } vector<vector<int>> g(n); deque<int> a, b; a.pb(0); for(int i = 1; i < n; ++i){ if(get(a.back(), i)){ a.pb(i); }else if(!b.empty() && get(b.back(), i)){ b.pb(i); }else{ if(b.empty()) b.pb(i); else{ reverse(all(b)); for(int x: b) a.pb(x); b.clear(); b.pb(i); } } // for(int x:) } if(b.size()>a.size())swap(a,b); vi A(all(a)); vi B(all(b)); if(B.empty()) return A; if(are_connected(A, B) == 0){ // for(int i = 0 ; i + 1 < A.size(); ++i) assert(are_connected(vi{A[i]}, vi{A[i+1]})); return A; } int u = -1, v; if(get(a[0], a.back()) == 0){ if(get(a[0], b.back()) == 1){ reverse(all(b)); for(int x: b) a.push_front(x); }else{ reverse(all(b)); for(int x: b) a.pb(x); } }else{ // cout << "f" << endl; int ul = 0, ur = int(b.size()) - 1, ub = -1; vi aa(all(a)); if(are_connected(vi{b.back()}, aa)){ ub = b.size() - 1; }else{ while(ul <= ur){ int um = ul+ur>>1; vi z; for(int j = 0; j <= um; ++j) z.pb(b[j]); if(are_connected(z, aa)){ ub = um; ur = um - 1; }else ul = um + 1; } } if(ub == -1){ assert(false); return aa; } ul = 0, ur = int(a.size()) - 1; int ua = -1; while(ul <= ur){ int um = ul+ur>>1; vi z; for(int j = 0; j <= um; ++j) z.pb(a[j]); if(are_connected(z, vi{b[ub]})){ ua = um; ur = um - 1; }else ul = um + 1; } if(ua == -1){ assert(false); vi res(all(a)); return res; } int uu = b[ub]; if(ub != b.size() - 1){ while(b.front() != uu){ int x = b.front(); b.pop_front(); b.pb(x); } }else reverse(all(b)); u = a[ua]; while(a.front() != u){ int x = a.front(); a.pop_front(); a.pb(x); } for(int x: b) a.push_front(x); } vi res(all(a)); return res; }

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:112:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int um = ul+ur>>1;
      |                  ~~^~~
longesttrip.cpp:127:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |       int um = ul+ur>>1;
      |                ~~^~~
longesttrip.cpp:142:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     if(ub != b.size() - 1){
      |        ~~~^~~~~~~~~~~~~~~
longesttrip.cpp:96:15: warning: unused variable 'v' [-Wunused-variable]
   96 |   int u = -1, v;
      |               ^
#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...