Submission #1059828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059828		mychecksedad	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	849 ms	1392 KiB

longesttrip

#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;
 
std::vector<int> longest_trip(int n, int D)
{
  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);
  vector<vector<bool>> is(n, vector<bool>(n));
  for(int i = 0; i < n; ++i){
    for(int j = i + 1; j < n; ++j){
      bool ok = are_connected(vi{i}, vi{j});
      if(ok){
        is[i][j] = is[j][i] = 1;
        g[i].pb(j);
        g[j].pb(i);
      }
    }
  }
  vector<vector<int>> S;
  for(int i = 0; i < n; ++i){
    if(g[i].empty()){
      vi res;
      for(int j = 0; j < n; ++j){
        if(j != i) res.pb(j);
      }
      return res;
    }
    bool okk = 0;
    for(auto &s: S){
      bool ok = 1;
      for(int x: s){
        if(is[x][i] == 0) ok = 0;
      }
      if(ok == 1){
        s.pb(i);
        okk = 1;
        break;
      }
    }
    if(okk == 0){
      S.pb(vi{i});
    }
  }
  if(S.size() == 2){
    for(int &x: S[0]){
      for(int &y: S[1]){
        if(is[x][y]){
          swap(x, S[0].back());
          swap(y, S[1][0]);
          vi res;
          for(int f: S[0]) res.pb(f);
          for(int f: S[1]) res.pb(f);
          return res;
        }   
      }
    }
    if(S[0].size() > S[1].size()) return S[0];
    return S[1];
  }
  vi res;
  int o = 0;
  for(int i = 0; i < S.size(); ++i){
    if(S[i].size() == 1){
      if(o == 0){
        S[0].swap(S[i]);
        ++o;
      }else if(o == 1){
        S.back().swap(S[i]);
        o += 2;
        break;
      }
    }
  }
  if(o == 1){
    bool ok = 0;
    for(int i = 1; i < S.size(); ++i){
      for(int x: S[i]){
        if(is[x][S[0][0]]){
          ok = 1;
          break;
        }
      }
      if(ok){
        S[1].swap(S[i]);
        break;
      }
    }
    if(!ok) assert(false);
  }else if(o == 2){
    for(int i = 0; i + 1 < S.size(); ++i){
      bool ok = 0;
      for(int x: S[i]){
        if(is[x][S.back()[0]]){
          ok = 1;
          break;
        }
      }
      if(ok){
        S[int(S.size()) - 2].swap(S[i]);
        break;
      }
    }
  }else if(o == 3 && S.size() > 3){
    vector<bool> b(S.size());
    vector<bool> b2(S.size());
    for(int i = 1; i < S.size(); ++i){
      bool ok = 0;
      for(int x: S[i]){
        if(is[x][S[0][0]]){
          ok = 1;
          break;
        }
      }
      if(ok){
        b[i] = 1;
      }
    }
    for(int i = 0; i + 1 < S.size(); ++i){
      bool ok = 0;
      for(int x: S[i]){
        if(is[x][S.back()[0]]){
          ok = 1;
          break;
        }
      }
      if(ok){
        b2[i] = 1;
        break;
      }
    }
    bool okk = 0;
    for(int i = 0; i < S.size(); ++i){
      for(int j = 0; j < S.size(); ++j){
        if(i == j) continue;
        if(b[i] && b2[j]){
          S[i].swap(S[1]);
          if(j == 1){
            S[int(S.size()) - 2].swap(S[i]);
          }else{
            S[int(S.size()) - 2].swap(S[j]);
          }
          okk = 1;
          break;
        }
      }
      if(okk) break;
    }
    if(!okk) assert(false);
  }
  for(int i = 0; i < S.size(); ++i){
    if(S[i].size() == 1){
      res.pb(S[i][0]);
      continue;
    }
    vi nxt;
    if(i + 1 < S.size()){
      nxt = S[i + 1];
    }
    if(nxt.empty()){
      for(int x: S[i]) res.pb(x);
    }else{
      bool ok = 0;
      for(int j = 1; j < S[i].size(); ++j){
        for(int l = 0; l < S[i + 1].size(); ++l){
          if(is[S[i][j]][S[i + 1][l]]){
            swap(S[i][j], S[i].back());
            swap(S[i + 1][l], S[i + 1][0]);
            ok = 1;
            break;
          }
        }
        if(ok) break;
      }
      for(int x: S[i]) res.pb(x);
    }
  }
  return res;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int i = 0; i < S.size(); ++i){
      |                  ~~^~~~~~~~~~
longesttrip.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i = 1; i < S.size(); ++i){
      |                    ~~^~~~~~~~~~
longesttrip.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int i = 0; i + 1 < S.size(); ++i){
      |                    ~~~~~~^~~~~~~~~~
longesttrip.cpp:147:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i = 1; i < S.size(); ++i){
      |                    ~~^~~~~~~~~~
longesttrip.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i = 0; i + 1 < S.size(); ++i){
      |                    ~~~~~~^~~~~~~~~~
longesttrip.cpp:173:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for(int i = 0; i < S.size(); ++i){
      |                    ~~^~~~~~~~~~
longesttrip.cpp:174:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |       for(int j = 0; j < S.size(); ++j){
      |                      ~~^~~~~~~~~~
longesttrip.cpp:191:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |   for(int i = 0; i < S.size(); ++i){
      |                  ~~^~~~~~~~~~
longesttrip.cpp:197:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     if(i + 1 < S.size()){
      |        ~~~~~~^~~~~~~~~~
longesttrip.cpp:204:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |       for(int j = 1; j < S[i].size(); ++j){
      |                      ~~^~~~~~~~~~~~~
longesttrip.cpp:205:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |         for(int l = 0; l < S[i + 1].size(); ++l){
      |                        ~~^~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60