oj.uz

Submission #577401

# Submission time Handle Problem Language Result Execution time Memory
577401 2022-06-14T17:28:37 Z Sam_a17 Factories (JOI14_factories) C++14
100 / 100
 6004 ms 283784 KB 
#include <bits/stdc++.h>
#include "factories.h"
// #include "garder.cpp"
using namespace std;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
// #define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 

const int maxN = 5e5 + 10, LOG = 27;
vector<pair<int, long long>> adj[maxN];
int sz[maxN], up[maxN][LOG], depth[maxN], compSize, p[maxN];
long long distn[maxN][LOG], dist[maxN], sub[maxN], lvl[maxN];
bool used[maxN];

void dfs_lca(int node, int parent) {
  for(auto i: adj[node]) {
    if(i.first == parent) continue;
    up[i.first][0] = node;
    for(int j = 1; j < LOG; j++) {
      up[i.first][j] = up[up[i.first][j - 1]][j - 1];
    }
    dist[i.first] = dist[node] + i.second; 
    depth[i.first] = depth[node] + 1;
    dfs_lca(i.first, node);
  }
}

int lca(int a, int b) {
  if(a == b) {
    return a;
  }
 
  if(depth[a] < depth[b]) {
    swap(a, b);
  }
 
  int delta = depth[a] - depth[b];
 
  for(int i = 0; i < LOG; i++) {
    if(delta & (1 << i)) {
      a = up[a][i];
    }
  }
 
  if(a == b) {
    return a;
  }
 
  for(int i = LOG - 1; i >= 0; i--) {
    if(up[a][i] != up[b][i]) {
      a = up[a][i], b = up[b][i];
    }
  }
 
  return up[a][0];
}

long long distance(int a, int b) {
  return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

int dfs_sz(int node, int parent) {
  sz[node] = 1, compSize++;
  for(auto i: adj[node]) {
    if(i.first == parent || used[i.first]) continue;
    sz[node] += dfs_sz(i.first, node);
  }
  return sz[node];
}
 
int get_centroid(int node, int parent) {
  for(auto i: adj[node]) {
    if(i.first == parent || used[i.first]) continue;
    if(2 * sz[i.first] > compSize) {
      return get_centroid(i.first, node);
    }
  }
  return node;
}
 
int find_centroid(int node, int parent) {
  compSize = 0;
  dfs_sz(node, 0);
  int centroid = get_centroid(node, 0);
  return centroid;
}
 
void centroid_decomposition() {
  queue<pair<pair<int, int>, int>> q;
  q.push({{1, 0}, 1});
  dfs_lca(1, 0);

  while(!q.empty()) {
    auto u = q.front();
    q.pop();
 
    int centroid = find_centroid(u.first.first, 0);
    lvl[centroid] = u.second;

    if(u.second) {
      p[centroid] = u.first.second;

      int curr = centroid;
      while(curr) {
        distn[centroid][lvl[curr]] = distance(centroid, curr);
        // dbg(distn[centroid][lvl[curr]])
        // dbg(centroid) dbg(curr)
        curr = p[curr];
      }
    }
 
    used[centroid] = true;
    for(auto i: adj[centroid]) {
      if(used[i.first]) continue;
      q.push({{i.first, centroid}, u.second + 1});
    }
  }
}

void Init(int N, int A[], int B[], int D[]) {
  for(int i = 0; i < N - 1; i++) {
    int a = A[i], b = B[i], c = D[i];
    a++, b++;

    adj[a].push_back({b, c});
    adj[b].push_back({a, c}); 

  }

  for(int i = 0; i <= N; i++) {
    sub[i] = 1e15;    
  }

  centroid_decomposition();
}

void upd(int node) {
  int curr = node;
  while(curr) {
    sub[curr] = min(sub[curr], distn[node][lvl[curr]]);
    curr = p[curr];
  }
}

void clr(int node) {
  int curr = node;
  while(curr) {
    sub[curr] = 1e15;
    curr = p[curr];
  }
}

long long qry(int node) {
  long long answ = sub[node], curr = node;
  while(curr) {
    answ = min(answ, sub[curr] + distn[node][lvl[curr]]);
    curr = p[curr];
  }
  return answ;
}

long long Query(int S, int X[], int T, int Y[]) {
  long long answ = 1e15;
  for(int i = 0; i < S; i++) {
    upd(X[i] + 1);
  }

  for(int i = 0; i < T; i++) {
    answ = min(answ, qry(Y[i] + 1));
  }

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

  return answ;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12756 KB Output is correct
2 Correct 262 ms 25992 KB Output is correct
3 Correct 285 ms 26228 KB Output is correct
4 Correct 290 ms 26200 KB Output is correct
5 Correct 321 ms 26536 KB Output is correct
6 Correct 202 ms 26172 KB Output is correct
7 Correct 296 ms 26248 KB Output is correct
8 Correct 307 ms 26148 KB Output is correct
9 Correct 305 ms 26608 KB Output is correct
10 Correct 193 ms 26032 KB Output is correct
11 Correct 305 ms 26000 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12460 KB Output is correct
2 Correct 2281 ms 229400 KB Output is correct
3 Correct 3908 ms 233240 KB Output is correct
4 Correct 802 ms 231152 KB Output is correct
5 Correct 5333 ms 262752 KB Output is correct
6 Correct 4100 ms 252492 KB Output is correct
7 Correct 1018 ms 78048 KB Output is correct
8 Correct 378 ms 78668 KB Output is correct
9 Correct 1262 ms 82868 KB Output is correct
10 Correct 1022 ms 79544 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12756 KB Output is correct
2 Correct 262 ms 25992 KB Output is correct
3 Correct 285 ms 26228 KB Output is correct
4 Correct 290 ms 26200 KB Output is correct
5 Correct 321 ms 26536 KB Output is correct
6 Correct 202 ms 26172 KB Output is correct
7 Correct 296 ms 26248 KB Output is correct
8 Correct 307 ms 26148 KB Output is correct
9 Correct 305 ms 26608 KB Output is correct
10 Correct 193 ms 26032 KB Output is correct
11 Correct 305 ms 26000 KB Output is correct
12 Correct 7 ms 12460 KB Output is correct
13 Correct 2281 ms 229400 KB Output is correct
14 Correct 3908 ms 233240 KB Output is correct
15 Correct 802 ms 231152 KB Output is correct
16 Correct 5333 ms 262752 KB Output is correct
17 Correct 4100 ms 252492 KB Output is correct
18 Correct 1018 ms 78048 KB Output is correct
19 Correct 378 ms 78668 KB Output is correct
20 Correct 1262 ms 82868 KB Output is correct
21 Correct 1022 ms 79544 KB Output is correct
22 Correct 2584 ms 254360 KB Output is correct
23 Correct 2804 ms 257060 KB Output is correct
24 Correct 4528 ms 258388 KB Output is correct
25 Correct 4429 ms 261812 KB Output is correct
26 Correct 4575 ms 258796 KB Output is correct
27 Correct 6004 ms 283784 KB Output is correct
28 Correct 975 ms 259468 KB Output is correct
29 Correct 4552 ms 258572 KB Output is correct
30 Correct 4413 ms 257732 KB Output is correct
31 Correct 4568 ms 258616 KB Output is correct
32 Correct 1255 ms 83812 KB Output is correct
33 Correct 441 ms 79200 KB Output is correct
34 Correct 715 ms 75520 KB Output is correct
35 Correct 739 ms 75312 KB Output is correct
36 Correct 1002 ms 76484 KB Output is correct
37 Correct 1050 ms 76556 KB Output is correct