oj.uz

Submission #1060356

# Submission time Handle Problem Language Result Execution time Memory
1060356 2024-08-15T13:20:38 Z mychecksedad Longest Trip (IOI23_longesttrip) C++17
15 / 100
 880 ms 1432 KB 
#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() == 1) return S[0];
  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];
  }
  
  deque<int> a, b;
  a.pb(0);
  for(int i = 1; i < n; ++i){
    if(is[a[0]][i]){
      a.push_front(i);
    }else if(is[a.back()][i]){
      a.pb(i);
    }else{
      if(b.empty()) b.pb(i);
      else{
        if(is[b[0]][i]){
          b.push_front(i);
        }else if(is[b.back()][i]){
          b.pb(i);
        }else{
          if(is[a.back()][b[0]]){
            for(int x: b) a.pb(x);
            b.clear();
            b.pb(i);
          }else{
            assert(false);
          }
        }
      }
    }
  }
  if(b.size()>a.size())swap(a,b);

  int u = -1, v;

  while(a.size() < n){
    if(is[a[0]][a.back()] == 0){
      if(is[a[0]][b.back()] == 1){
        a.push_front(b.back());
        b.pop_back();
      }else{
        a.pb(b.back());
        b.pop_back();
      }
    }else{
      bool ok = 1;
      if(u == -1){
        for(int i = 0; i < a.size(); ++i){
          for(int j = i + 1; j < a.size(); ++j){
            // int u = a[i], v = a[j];
            if(is[u][v] == 0){
              u = a[i], v = a[j];
              break;
              if(is[b.back()][u] == 1){
                while(a.front() != u){
                  int x = a.front();
                  a.pop_front();
                  a.pb(x);
                }
                a.push_front(b.back());
                b.pop_back();
              }else{
                while(a.front() != v){
                  int x = a.front();
                  a.pop_front();
                  a.pb(x);
                }
                a.push_front(b.back());
                b.pop_back();
              }
              ok = 1;
              break;
            }
          }

          if(u != -1) break;
        }
      }
      if(is[b.back()][u] == 1){
        while(a.front() != u){
          int x = a.front();
          a.pop_front();
          a.pb(x);
        }
        a.push_front(b.back());
        b.pop_back();
      }else{
        while(a.front() != v){
          int x = a.front();
          a.pop_front();
          a.pb(x);
        }
        a.push_front(b.back());
        b.pop_back();
      }
    }
  }
  vi res(all(a));
  return res;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:133:18: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  133 |   while(a.size() < n){
      |         ~~~~~~~~~^~~
longesttrip.cpp:145:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for(int i = 0; i < a.size(); ++i){
      |                        ~~^~~~~~~~~~
longesttrip.cpp:146:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |           for(int j = i + 1; j < a.size(); ++j){
      |                              ~~^~~~~~~~~~
longesttrip.cpp:143:12: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  143 |       bool ok = 1;
      |            ^~
longesttrip.cpp:148:23: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |             if(is[u][v] == 0){
      |                       ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 210 ms 1024 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 7 ms 344 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 135 ms 592 KB Output is correct
4 Correct 407 ms 740 KB Output is correct
5 Correct 876 ms 1352 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 141 ms 344 KB Output is correct
9 Correct 330 ms 860 KB Output is correct
10 Correct 818 ms 996 KB Output is correct
11 Correct 762 ms 776 KB Output is correct
12 Correct 798 ms 756 KB Output is correct
13 Correct 808 ms 976 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Runtime error 2 ms 344 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 143 ms 440 KB Output is partially correct
4 Partially correct 395 ms 476 KB Output is partially correct
5 Partially correct 825 ms 1124 KB Output is partially correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 140 ms 600 KB Output is partially correct
9 Partially correct 321 ms 488 KB Output is partially correct
10 Partially correct 856 ms 968 KB Output is partially correct
11 Partially correct 790 ms 1016 KB Output is partially correct
12 Partially correct 880 ms 740 KB Output is partially correct
13 Partially correct 799 ms 1432 KB Output is partially correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Runtime error 2 ms 344 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -