oj.uz

답안 #784795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
784795 2023-07-16T14:31:46 Z cadmiumsky 고대 책들 (IOI17_books) C++17
12 / 100
 14 ms 23788 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<pii> g[nmax];
  void addedge(int x, int y, int z) {
    g[x].emplace_back(y, z);
  }
  priority_queue<pii, vector<pii>, greater<pii>> heap;
  vector<int> arriv, occ;
  vector<int> dijkstra(int s = -1) {
    arriv.resize(n);
    occ.resize(n);
    fill(all(occ), 0);
    if(s != -1) {
      fill(all(arriv), inf);
      heap.emplace(0, s);
      arriv[s] = 0;
    }
    else {
      for(int i = 0; i < n; i++)
        heap.emplace(arriv[i], i);
    }
    while(!heap.empty()) {
      auto [c, node] = heap.top();
      heap.pop();
      if(occ[node]) continue;
      occ[node] = 1;
      for(auto [x, e] : g[node]) {
        if(arriv[x] > c + e) {
          arriv[x] = c + e;
          heap.emplace(arriv[x], x);
        }
      }
    }
    return arriv;
  }
}

long long minimum_walk(std::vector<int> p, int s) {
  n = sz(p);
  vector<int> col(n, 0);
  vector<int> rs(n + 2, 0), ls(n + 2, 0);
  int flag = 0;
  
  multiset<int> lhf;
  
  ll sum = 0;
  
  for(int i = 0; i < n; i++) {
    if(col[i] == 0) {
      flag++;
      int x = i, cnt = 0;
      set<int> vals;
      while(col[x] != flag) {
        col[x] = flag;
        sum += abs(x - p[x]);
        x = p[x];
        cnt++;
        vals.emplace(x);
      }
      int L = *vals.begin();
      int R = *vals.rbegin();
      flag++;
      x = i;
      while(col[x] != flag) {
        col[x] = flag;
        G::addedge(L, x, 0);
        G::addedge(R, x, 0);
        x = p[x];
      }
    }
    if(i > 0)
      G::addedge(i - 1, i, 2),
      G::addedge(i, i - 1, 2);
  }
  
  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 < n; i++) {
    G::arriv[i] = fl[i] + fr[i];
  }
  auto rez = G::dijkstra();

  
  
  return sum + rez[s];
}

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

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23784 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 11 ms 23684 KB Output is correct
4 Correct 10 ms 23680 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 10 ms 23788 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 10 ms 23764 KB Output is correct
10 Correct 12 ms 23728 KB Output is correct
11 Correct 11 ms 23776 KB Output is correct
12 Correct 10 ms 23696 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 11 ms 23760 KB Output is correct
15 Correct 12 ms 23696 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23784 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 11 ms 23684 KB Output is correct
4 Correct 10 ms 23680 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 10 ms 23788 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 10 ms 23764 KB Output is correct
10 Correct 12 ms 23728 KB Output is correct
11 Correct 11 ms 23776 KB Output is correct
12 Correct 10 ms 23696 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 11 ms 23760 KB Output is correct
15 Correct 12 ms 23696 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Incorrect 14 ms 23788 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23784 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 11 ms 23684 KB Output is correct
4 Correct 10 ms 23680 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 10 ms 23788 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 10 ms 23764 KB Output is correct
10 Correct 12 ms 23728 KB Output is correct
11 Correct 11 ms 23776 KB Output is correct
12 Correct 10 ms 23696 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 11 ms 23760 KB Output is correct
15 Correct 12 ms 23696 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Incorrect 14 ms 23788 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3312'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23784 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 11 ms 23684 KB Output is correct
4 Correct 10 ms 23680 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 10 ms 23788 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 10 ms 23764 KB Output is correct
10 Correct 12 ms 23728 KB Output is correct
11 Correct 11 ms 23776 KB Output is correct
12 Correct 10 ms 23696 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 11 ms 23760 KB Output is correct
15 Correct 12 ms 23696 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Incorrect 14 ms 23788 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -