oj.uz

Submission #887406

# Submission time Handle Problem Language Result Execution time Memory
887406 2023-12-14T12:26:22 Z Zero_OP Factories (JOI14_factories) C++14
100 / 100
 3727 ms 191756 KB 
#include<bits/stdc++.h>
#include<factories.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
  if(a > b) return a = b, true;
  return false;
}

template<class T> bool maximize(T& a, T b){
  if(a < b) return a = b, true;
  return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 5e5 + 5;
const ll inf = 1e18;

int n, q, h[N], pos[N], rmq[20][N + N], par[N], timerDFS, sz[N];
ll depth[N], dp[N];
bool del[N];
vector<pair<int, int>> g[N];

void dfs(int u, int e){
  rmq[0][pos[u] = timerDFS++] = u;
  for(auto [v, w] : g[u]) if(v != e){
    h[v] = h[u] + 1;
    depth[v] = depth[u] + w;
    dfs(v, u);
    rmq[0][timerDFS++] = u;
  }
}

int combine(int u, int v){
  return h[u] < h[v] ? u : v;
}

void prepareRMQ(){
  for(int i = 1; (1 << i) <= timerDFS; ++i){
    for(int j = 0; j + (1 << i) <= timerDFS; ++j){
      rmq[i][j] = combine(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
    }
  }
}

int getLCA(int u, int v){
  u = pos[u], v = pos[v];
  if(u > v) swap(u, v);
  int b = __lg(v - u + 1);
  return combine(rmq[b][u], rmq[b][v - (1 << b) + 1]);
}

ll getDist(int u, int v){
  return depth[u] + depth[v] - 2 * depth[getLCA(u, v)];
}

int dfsSize(int u, int e){
  sz[u] = 1;
  for(auto [v, w] : g[u]) if(v != e and !del[v]){
    sz[u] += dfsSize(v, u);
  }
  return sz[u];
}

int getCentroid(int u, int e, int target){
  for(auto [v, w] : g[u]) if(v != e and !del[v] and sz[v] * 2 > target){
    return getCentroid(v, u, target);
  }
  return u;
}

void decompose(int u, int e){
  int c = getCentroid(u, e, dfsSize(u, e));
  par[c] = e;
  del[c] = true;
  for(auto [v, w] : g[c]) if(!del[v]){
    decompose(v, c);
  }
}

void update(int u){
  dp[u] = 0;
  int nxt = u;
  while(par[nxt] != -1){
    nxt = par[nxt];
    minimize(dp[nxt], getDist(nxt, u));
  }
}

ll query(int u){
  ll ans = dp[u];
  int nxt = u;
  while(par[nxt] != -1){
    nxt = par[nxt];
    minimize(ans, dp[nxt] + getDist(nxt, u));
  }
  return ans;
}

void resetData(int u){
  dp[u] = inf;
  while(par[u] != -1){
    u = par[u];
    dp[u] = inf;
  }
}

void Init(int N, int A[], int B[], int D[]){
  n = N;
  for(int i = 0; i + 1 < n; ++i){
    g[A[i]].push_back({B[i], D[i]});
    g[B[i]].push_back({A[i], D[i]});
  }

  fill(dp, dp + n, inf);
  dfs(0, -1);
  decompose(0, -1);
  prepareRMQ();
}

long long Query(int S, int X[], int T, int Y[]){
  ll ans = inf;
  for(int i = 0; i < S; ++i){
    update(X[i]);
  }

  for(int i = 0; i < T; ++i){
    minimize(ans, query(Y[i]));
  }

  for(int i = 0; i < S; ++i){
    resetData(X[i]);
  }

  return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:33:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for(auto [v, w] : g[u]) if(v != e){
      |            ^
factories.cpp: In function 'int dfsSize(int, int)':
factories.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |   for(auto [v, w] : g[u]) if(v != e and !del[v]){
      |            ^
factories.cpp: In function 'int getCentroid(int, int, int)':
factories.cpp:73:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |   for(auto [v, w] : g[u]) if(v != e and !del[v] and sz[v] * 2 > target){
      |            ^
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:83:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |   for(auto [v, w] : g[c]) if(!del[v]){
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 55896 KB Output is correct
2 Correct 285 ms 77904 KB Output is correct
3 Correct 363 ms 78164 KB Output is correct
4 Correct 353 ms 77904 KB Output is correct
5 Correct 442 ms 78376 KB Output is correct
6 Correct 158 ms 77908 KB Output is correct
7 Correct 356 ms 78304 KB Output is correct
8 Correct 362 ms 77908 KB Output is correct
9 Correct 434 ms 78324 KB Output is correct
10 Correct 157 ms 77908 KB Output is correct
11 Correct 360 ms 78168 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55900 KB Output is correct
2 Correct 1388 ms 167132 KB Output is correct
3 Correct 1905 ms 169300 KB Output is correct
4 Correct 412 ms 167604 KB Output is correct
5 Correct 2745 ms 191532 KB Output is correct
6 Correct 1942 ms 170068 KB Output is correct
7 Correct 779 ms 108924 KB Output is correct
8 Correct 247 ms 108784 KB Output is correct
9 Correct 937 ms 111496 KB Output is correct
10 Correct 775 ms 109396 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 55896 KB Output is correct
2 Correct 285 ms 77904 KB Output is correct
3 Correct 363 ms 78164 KB Output is correct
4 Correct 353 ms 77904 KB Output is correct
5 Correct 442 ms 78376 KB Output is correct
6 Correct 158 ms 77908 KB Output is correct
7 Correct 356 ms 78304 KB Output is correct
8 Correct 362 ms 77908 KB Output is correct
9 Correct 434 ms 78324 KB Output is correct
10 Correct 157 ms 77908 KB Output is correct
11 Correct 360 ms 78168 KB Output is correct
12 Correct 8 ms 55900 KB Output is correct
13 Correct 1388 ms 167132 KB Output is correct
14 Correct 1905 ms 169300 KB Output is correct
15 Correct 412 ms 167604 KB Output is correct
16 Correct 2745 ms 191532 KB Output is correct
17 Correct 1942 ms 170068 KB Output is correct
18 Correct 779 ms 108924 KB Output is correct
19 Correct 247 ms 108784 KB Output is correct
20 Correct 937 ms 111496 KB Output is correct
21 Correct 775 ms 109396 KB Output is correct
22 Correct 1959 ms 171840 KB Output is correct
23 Correct 1989 ms 173064 KB Output is correct
24 Correct 2915 ms 174076 KB Output is correct
25 Correct 2832 ms 176360 KB Output is correct
26 Correct 2703 ms 174420 KB Output is correct
27 Correct 3727 ms 191756 KB Output is correct
28 Correct 514 ms 174260 KB Output is correct
29 Correct 2750 ms 174164 KB Output is correct
30 Correct 2664 ms 173656 KB Output is correct
31 Correct 2731 ms 174272 KB Output is correct
32 Correct 930 ms 112144 KB Output is correct
33 Correct 246 ms 108772 KB Output is correct
34 Correct 533 ms 107604 KB Output is correct
35 Correct 546 ms 107352 KB Output is correct
36 Correct 728 ms 107860 KB Output is correct
37 Correct 752 ms 107832 KB Output is correct