oj.uz

Submission #1059815

# Submission time Handle Problem Language Result Execution time Memory
1059815 2024-08-15T08:26:00 Z mychecksedad Longest Trip (IOI23_longesttrip) C++17
15 / 100
 868 ms 1208 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() == 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, cur = 0;
  for(int i = 0; i < S.size(); ++i){
    if(S[i].size() == 1){
      // ++cur;
      if(o == 0){
        // S[0].swap(S[i]);
        ++o;
        assert(false);
      }else if(o == 1){
        // S.back().swap(S[i]);
        ++o;
        // break;
        // 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

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:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(int i = 0; i < S.size(); ++i){
      |                  ~~^~~~~~~~~~
longesttrip.cpp:124:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     if(i + 1 < S.size()){
      |        ~~~~~~^~~~~~~~~~
longesttrip.cpp:131:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |       for(int j = 1; j < S[i].size(); ++j){
      |                      ~~^~~~~~~~~~~~~
longesttrip.cpp:132:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for(int l = 0; l < S[i + 1].size(); ++l){
      |                        ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:102:14: warning: unused variable 'cur' [-Wunused-variable]
  102 |   int o = 0, cur = 0;
      |              ^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 185 ms 1080 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 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 8 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 8 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 26 ms 344 KB Output is correct
3 Correct 183 ms 440 KB Output is correct
4 Correct 443 ms 460 KB Output is correct
5 Correct 759 ms 800 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Correct 140 ms 344 KB Output is correct
9 Correct 307 ms 500 KB Output is correct
10 Correct 809 ms 812 KB Output is correct
11 Correct 863 ms 984 KB Output is correct
12 Correct 827 ms 736 KB Output is correct
13 Correct 844 ms 820 KB Output is correct
14 Correct 9 ms 344 KB Output is correct
15 Runtime error 2 ms 344 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 148 ms 444 KB Output is partially correct
4 Partially correct 388 ms 728 KB Output is partially correct
5 Partially correct 854 ms 1012 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 153 ms 440 KB Output is partially correct
9 Partially correct 309 ms 344 KB Output is partially correct
10 Partially correct 845 ms 1088 KB Output is partially correct
11 Partially correct 868 ms 1100 KB Output is partially correct
12 Partially correct 794 ms 988 KB Output is partially correct
13 Partially correct 851 ms 1208 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Runtime error 3 ms 600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -