oj.uz

Submission #784844

# Submission time Handle Problem Language Result Execution time Memory
784844 2023-07-16T15:18:32 Z cadmiumsky Ancient Books (IOI17_books) C++17
100 / 100
 1848 ms 366700 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e6 + 5, inf = 1e9 + 5;

int n;

namespace G {
  vector<vector<pii>> g;
  void init(int dim) { g.resize(dim, vector<pii>()); }
  int newnode() { g.emplace_back(); return sz(g) - 1; }
  void addedge(int x, int y, int z) {
    g[x].emplace_back(y, z);
  }
  
  namespace AINT {
    int aint[(nmax + nmax / 2) * 2];
    void init(int node = 1, int cl = 0, int cr = n - 1) {
      if(cl == cr) {
        aint[node] = cl;
        return;
      }
      int mid = cl + cr >> 1;
      init(2 * node, cl, mid);
      init(2 * node + 1, mid + 1, cr);
      aint[node] = newnode();
      addedge(aint[2 * node], aint[node], 0);
      addedge(aint[2 * node + 1], aint[node], 0);
      return;
    }
    void pushto(int val, int l, int r, int node = 1, int cl = 0, int cr = n - 1) {
      if(r < cl || cr < l) return;;
      if(l <= cl && cr <= r) {
        addedge(aint[node], val, 0);
        return;
      }
      int mid = cl + cr >> 1;
      pushto(val, l, r, 2 * node, cl, mid);
      pushto(val, l, r, 2 * node + 1, mid + 1, cr);
    }
  }
  
  vector<int> arriv, occ;
  vector<int> heap[nmax];
  vector<int> dijkstra(int s = -1) {
    arriv.resize(sz(g));
    occ.resize(sz(g));
    for(int i = 0; i <= n + 2; i++) heap[i].clear();
    //cerr << sz(arriv) << ' ' << sz(g) << '\n';
    fill(all(occ), 0);
    if(s != -1) {
      fill(all(arriv), inf);
      heap[0].emplace_back(s);
      arriv[s] = 0;
    }
    else {
      for(int i = 0; i < sz(g); i++)
        arriv[i] = min(arriv[i], n + 2),
        heap[arriv[i]].emplace_back(i);
    }
    for(int i = 0; i < n + 2; i++) {
      int c = i;
      for(int j = 0; j < sz(heap[i]); j++) {
        auto node = heap[i][j];
        if(occ[node]) continue;
        occ[node] = 1;
        for(auto [x, e] : g[node]) {
          if(arriv[x] > c + e) {
            arriv[x] = c + e;
            heap[arriv[x]].emplace_back(x);
          }
        }
      }
    }
    return arriv;
  }
}

long long minimum_walk(std::vector<signed> p, signed s) {
  n = sz(p);
  vector<int> col(n, 0);
  vector<int> rs(n + 2, 0), ls(n + 2, 0);
  int flag = 0;
  
  ll sum = 0;
  
  G::init(n);
  G::AINT::init();
  
  for(int i = 0; i < n; i++) {
    if(col[i] == 0 && p[i] != i) {
      flag++;
      int x = i, cnt = 0;
      int L = n;
      int R = -1;
      while(col[x] != flag) {
        col[x] = flag;
        L = min(x, L);
        R = max(x, R);
        sum += abs(x - p[x]);
        x = p[x];
        cnt++;
      }
      flag++;
      x = i;
      int u = G::newnode();
      G::AINT::pushto(u, L, R);
      while(col[x] != flag) {
        col[x] = flag;
        G::addedge(u, x, 0);
        x = p[x];
      }
    }
    if(i > 0)
      G::addedge(i - 1, i, 1),
      G::addedge(i, i - 1, 1);
  }
  
  int sl = 0, sr = n - 1;
  while(p[sl] == sl && sl < s) sl++;
  while(p[sr] == sr && sr > s) sr--;
  
  auto fl = G::dijkstra(sl), fr = G::dijkstra(sr);
  for(int i = 0; i < sz(G::g); i++) {
    G::arriv[i] = fl[i] + fr[i];
  }
  auto rez = G::dijkstra();
  
  return sum + (ll)rez[s] * 2;
}
#undef int

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Compilation message

books.cpp: In function 'void G::AINT::init(int, int, int)':
books.cpp:33:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
books.cpp: In function 'void G::AINT::pushto(int, int, int, int, int, int)':
books.cpp:47:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23692 KB Output is correct
3 Correct 13 ms 23792 KB Output is correct
4 Correct 12 ms 23744 KB Output is correct
5 Correct 14 ms 23788 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23780 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 13 ms 23720 KB Output is correct
12 Correct 12 ms 23736 KB Output is correct
13 Correct 13 ms 23772 KB Output is correct
14 Correct 13 ms 23788 KB Output is correct
15 Correct 13 ms 23692 KB Output is correct
16 Correct 12 ms 23748 KB Output is correct
17 Correct 12 ms 23692 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23692 KB Output is correct
3 Correct 13 ms 23792 KB Output is correct
4 Correct 12 ms 23744 KB Output is correct
5 Correct 14 ms 23788 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23780 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 13 ms 23720 KB Output is correct
12 Correct 12 ms 23736 KB Output is correct
13 Correct 13 ms 23772 KB Output is correct
14 Correct 13 ms 23788 KB Output is correct
15 Correct 13 ms 23692 KB Output is correct
16 Correct 12 ms 23748 KB Output is correct
17 Correct 12 ms 23692 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 13 ms 24020 KB Output is correct
20 Correct 15 ms 23984 KB Output is correct
21 Correct 13 ms 23964 KB Output is correct
22 Correct 13 ms 23928 KB Output is correct
23 Correct 13 ms 24020 KB Output is correct
24 Correct 13 ms 24020 KB Output is correct
25 Correct 13 ms 24020 KB Output is correct
26 Correct 13 ms 24020 KB Output is correct
27 Correct 13 ms 24052 KB Output is correct
28 Correct 13 ms 24020 KB Output is correct
29 Correct 13 ms 24056 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23692 KB Output is correct
3 Correct 13 ms 23792 KB Output is correct
4 Correct 12 ms 23744 KB Output is correct
5 Correct 14 ms 23788 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23780 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 13 ms 23720 KB Output is correct
12 Correct 12 ms 23736 KB Output is correct
13 Correct 13 ms 23772 KB Output is correct
14 Correct 13 ms 23788 KB Output is correct
15 Correct 13 ms 23692 KB Output is correct
16 Correct 12 ms 23748 KB Output is correct
17 Correct 12 ms 23692 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 13 ms 24020 KB Output is correct
20 Correct 15 ms 23984 KB Output is correct
21 Correct 13 ms 23964 KB Output is correct
22 Correct 13 ms 23928 KB Output is correct
23 Correct 13 ms 24020 KB Output is correct
24 Correct 13 ms 24020 KB Output is correct
25 Correct 13 ms 24020 KB Output is correct
26 Correct 13 ms 24020 KB Output is correct
27 Correct 13 ms 24052 KB Output is correct
28 Correct 13 ms 24020 KB Output is correct
29 Correct 13 ms 24056 KB Output is correct
30 Correct 1224 ms 249288 KB Output is correct
31 Correct 1264 ms 255748 KB Output is correct
32 Correct 751 ms 265696 KB Output is correct
33 Correct 892 ms 285836 KB Output is correct
34 Correct 882 ms 285816 KB Output is correct
35 Correct 853 ms 287540 KB Output is correct
36 Correct 915 ms 289112 KB Output is correct
37 Correct 728 ms 281048 KB Output is correct
38 Correct 753 ms 267884 KB Output is correct
39 Correct 744 ms 267440 KB Output is correct
40 Correct 797 ms 264392 KB Output is correct
41 Correct 988 ms 270064 KB Output is correct
42 Correct 951 ms 273776 KB Output is correct
43 Correct 1787 ms 284272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24020 KB Output is correct
2 Correct 15 ms 24020 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Correct 13 ms 24012 KB Output is correct
5 Correct 16 ms 24016 KB Output is correct
6 Correct 14 ms 23984 KB Output is correct
7 Correct 13 ms 24020 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24020 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 15 ms 24104 KB Output is correct
12 Correct 13 ms 24100 KB Output is correct
13 Correct 14 ms 24064 KB Output is correct
14 Correct 14 ms 23996 KB Output is correct
15 Correct 13 ms 24060 KB Output is correct
16 Correct 13 ms 24020 KB Output is correct
17 Correct 13 ms 23980 KB Output is correct
18 Correct 13 ms 24020 KB Output is correct
19 Correct 14 ms 24068 KB Output is correct
20 Correct 13 ms 24020 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23692 KB Output is correct
3 Correct 13 ms 23792 KB Output is correct
4 Correct 12 ms 23744 KB Output is correct
5 Correct 14 ms 23788 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23780 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 13 ms 23720 KB Output is correct
12 Correct 12 ms 23736 KB Output is correct
13 Correct 13 ms 23772 KB Output is correct
14 Correct 13 ms 23788 KB Output is correct
15 Correct 13 ms 23692 KB Output is correct
16 Correct 12 ms 23748 KB Output is correct
17 Correct 12 ms 23692 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 13 ms 24020 KB Output is correct
20 Correct 15 ms 23984 KB Output is correct
21 Correct 13 ms 23964 KB Output is correct
22 Correct 13 ms 23928 KB Output is correct
23 Correct 13 ms 24020 KB Output is correct
24 Correct 13 ms 24020 KB Output is correct
25 Correct 13 ms 24020 KB Output is correct
26 Correct 13 ms 24020 KB Output is correct
27 Correct 13 ms 24052 KB Output is correct
28 Correct 13 ms 24020 KB Output is correct
29 Correct 13 ms 24056 KB Output is correct
30 Correct 1224 ms 249288 KB Output is correct
31 Correct 1264 ms 255748 KB Output is correct
32 Correct 751 ms 265696 KB Output is correct
33 Correct 892 ms 285836 KB Output is correct
34 Correct 882 ms 285816 KB Output is correct
35 Correct 853 ms 287540 KB Output is correct
36 Correct 915 ms 289112 KB Output is correct
37 Correct 728 ms 281048 KB Output is correct
38 Correct 753 ms 267884 KB Output is correct
39 Correct 744 ms 267440 KB Output is correct
40 Correct 797 ms 264392 KB Output is correct
41 Correct 988 ms 270064 KB Output is correct
42 Correct 951 ms 273776 KB Output is correct
43 Correct 1787 ms 284272 KB Output is correct
44 Correct 13 ms 24020 KB Output is correct
45 Correct 15 ms 24020 KB Output is correct
46 Correct 13 ms 24020 KB Output is correct
47 Correct 13 ms 24012 KB Output is correct
48 Correct 16 ms 24016 KB Output is correct
49 Correct 14 ms 23984 KB Output is correct
50 Correct 13 ms 24020 KB Output is correct
51 Correct 13 ms 24020 KB Output is correct
52 Correct 13 ms 24020 KB Output is correct
53 Correct 13 ms 24020 KB Output is correct
54 Correct 15 ms 24104 KB Output is correct
55 Correct 13 ms 24100 KB Output is correct
56 Correct 14 ms 24064 KB Output is correct
57 Correct 14 ms 23996 KB Output is correct
58 Correct 13 ms 24060 KB Output is correct
59 Correct 13 ms 24020 KB Output is correct
60 Correct 13 ms 23980 KB Output is correct
61 Correct 13 ms 24020 KB Output is correct
62 Correct 14 ms 24068 KB Output is correct
63 Correct 13 ms 24020 KB Output is correct
64 Correct 956 ms 267652 KB Output is correct
65 Correct 943 ms 266056 KB Output is correct
66 Correct 869 ms 269544 KB Output is correct
67 Correct 855 ms 267116 KB Output is correct
68 Correct 92 ms 48972 KB Output is correct
69 Correct 83 ms 48812 KB Output is correct
70 Correct 88 ms 48856 KB Output is correct
71 Correct 99 ms 48692 KB Output is correct
72 Correct 101 ms 48212 KB Output is correct
73 Correct 84 ms 48056 KB Output is correct
74 Correct 831 ms 285768 KB Output is correct
75 Correct 825 ms 285908 KB Output is correct
76 Correct 1848 ms 281532 KB Output is correct
77 Correct 1782 ms 284092 KB Output is correct
78 Correct 1735 ms 298032 KB Output is correct
79 Correct 1724 ms 297088 KB Output is correct
80 Correct 724 ms 266048 KB Output is correct
81 Correct 1181 ms 366700 KB Output is correct
82 Correct 1165 ms 366668 KB Output is correct
83 Correct 1062 ms 293336 KB Output is correct
84 Correct 1014 ms 289624 KB Output is correct
85 Correct 921 ms 279712 KB Output is correct
86 Correct 846 ms 274964 KB Output is correct
87 Correct 1031 ms 304164 KB Output is correct
88 Correct 1071 ms 305504 KB Output is correct
89 Correct 1047 ms 297536 KB Output is correct
90 Correct 750 ms 270068 KB Output is correct
91 Correct 741 ms 264604 KB Output is correct
92 Correct 845 ms 261552 KB Output is correct