oj.uz

Submission #1061148

# Submission time Handle Problem Language Result Execution time Memory
1061148 2024-08-16T06:40:01 Z mychecksedad Longest Trip (IOI23_longesttrip) C++17
100 / 100
 11 ms 856 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;
 
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

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;
      |               ^

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 600 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 5 ms 436 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 7 ms 600 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 5 ms 600 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 6 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 8 ms 600 KB Output is correct
6 Correct 8 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 8 ms 344 KB Output is correct
10 Correct 8 ms 600 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 6 ms 600 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 7 ms 344 KB Output is correct
18 Correct 7 ms 344 KB Output is correct
19 Correct 6 ms 344 KB Output is correct
20 Correct 8 ms 344 KB Output is correct
21 Correct 7 ms 856 KB Output is correct
22 Correct 6 ms 600 KB Output is correct
23 Correct 7 ms 600 KB Output is correct
24 Correct 6 ms 600 KB Output is correct
25 Correct 6 ms 344 KB Output is correct
26 Correct 5 ms 344 KB Output is correct
27 Correct 6 ms 344 KB Output is correct
28 Correct 5 ms 344 KB Output is correct
29 Correct 5 ms 344 KB Output is correct
30 Correct 7 ms 344 KB Output is correct
31 Correct 6 ms 344 KB Output is correct
32 Correct 10 ms 344 KB Output is correct
33 Correct 7 ms 344 KB Output is correct
34 Correct 8 ms 344 KB Output is correct
35 Correct 6 ms 344 KB Output is correct
36 Correct 6 ms 600 KB Output is correct
37 Correct 6 ms 600 KB Output is correct
38 Correct 8 ms 708 KB Output is correct
39 Correct 7 ms 712 KB Output is correct
40 Correct 7 ms 600 KB Output is correct
41 Correct 9 ms 600 KB Output is correct
42 Correct 9 ms 600 KB Output is correct
43 Correct 10 ms 600 KB Output is correct
44 Correct 7 ms 600 KB Output is correct
45 Correct 9 ms 344 KB Output is correct
46 Correct 8 ms 344 KB Output is correct
47 Correct 8 ms 344 KB Output is correct
48 Correct 8 ms 344 KB Output is correct
49 Correct 11 ms 344 KB Output is correct
50 Correct 6 ms 344 KB Output is correct
51 Correct 10 ms 344 KB Output is correct
52 Correct 8 ms 344 KB Output is correct
53 Correct 5 ms 344 KB Output is correct
54 Correct 6 ms 344 KB Output is correct
55 Correct 6 ms 344 KB Output is correct
56 Correct 7 ms 600 KB Output is correct
57 Correct 6 ms 600 KB Output is correct
58 Correct 7 ms 720 KB Output is correct
59 Correct 11 ms 600 KB Output is correct
60 Correct 8 ms 600 KB Output is correct
61 Correct 8 ms 716 KB Output is correct
62 Correct 9 ms 716 KB Output is correct
63 Correct 8 ms 600 KB Output is correct
64 Correct 8 ms 600 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 4 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 600 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 10 ms 344 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 9 ms 600 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 5 ms 600 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 7 ms 344 KB Output is correct
19 Correct 6 ms 344 KB Output is correct
20 Correct 7 ms 600 KB Output is correct
21 Correct 6 ms 344 KB Output is correct
22 Correct 7 ms 344 KB Output is correct
23 Correct 6 ms 344 KB Output is correct
24 Correct 6 ms 344 KB Output is correct
25 Correct 6 ms 344 KB Output is correct
26 Correct 6 ms 344 KB Output is correct
27 Correct 6 ms 344 KB Output is correct
28 Correct 6 ms 344 KB Output is correct
29 Correct 5 ms 344 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 6 ms 344 KB Output is correct
32 Correct 10 ms 344 KB Output is correct
33 Correct 8 ms 344 KB Output is correct
34 Correct 9 ms 344 KB Output is correct
35 Correct 8 ms 344 KB Output is correct
36 Correct 8 ms 344 KB Output is correct
37 Correct 6 ms 344 KB Output is correct
38 Correct 8 ms 344 KB Output is correct
39 Correct 8 ms 344 KB Output is correct
40 Correct 6 ms 344 KB Output is correct
41 Correct 6 ms 344 KB Output is correct
42 Correct 7 ms 344 KB Output is correct
43 Correct 6 ms 600 KB Output is correct
44 Correct 7 ms 600 KB Output is correct
45 Correct 7 ms 600 KB Output is correct
46 Correct 8 ms 600 KB Output is correct
47 Correct 5 ms 600 KB Output is correct
48 Correct 6 ms 600 KB Output is correct
49 Correct 6 ms 600 KB Output is correct
50 Correct 7 ms 600 KB Output is correct
51 Correct 6 ms 712 KB Output is correct
52 Correct 7 ms 600 KB Output is correct
53 Correct 7 ms 600 KB Output is correct
54 Correct 7 ms 856 KB Output is correct
55 Correct 7 ms 600 KB Output is correct
56 Correct 6 ms 712 KB Output is correct
57 Correct 6 ms 600 KB Output is correct
58 Correct 7 ms 716 KB Output is correct
59 Correct 6 ms 600 KB Output is correct
60 Correct 8 ms 600 KB Output is correct
61 Correct 8 ms 600 KB Output is correct
62 Correct 6 ms 600 KB Output is correct
63 Correct 6 ms 600 KB Output is correct
64 Correct 11 ms 600 KB Output is correct
65 Correct 7 ms 600 KB Output is correct
66 Correct 7 ms 600 KB Output is correct
67 Correct 10 ms 600 KB Output is correct
68 Correct 8 ms 600 KB Output is correct
69 Correct 8 ms 600 KB Output is correct
70 Correct 10 ms 600 KB Output is correct
71 Correct 6 ms 600 KB Output is correct
72 Correct 7 ms 720 KB Output is correct
73 Correct 7 ms 600 KB Output is correct
74 Correct 8 ms 716 KB Output is correct
75 Correct 10 ms 600 KB Output is correct
76 Correct 8 ms 716 KB Output is correct
77 Correct 8 ms 600 KB Output is correct
78 Correct 11 ms 600 KB Output is correct
79 Correct 7 ms 600 KB Output is correct
80 Correct 7 ms 712 KB Output is correct
81 Correct 10 ms 600 KB Output is correct
82 Correct 7 ms 600 KB Output is correct