oj.uz

Submission #533183

# Submission time Handle Problem Language Result Execution time Memory
533183 2022-03-05T04:55:42 Z cig32 Factories (JOI14_factories) C++17
100 / 100
 3614 ms 464008 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]);
long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]);

const int MAXN = 500003;
vector<pair<int, int> > adj[MAXN];

pair<int, signed> st[20][2*MAXN];

int tin[MAXN], tout[MAXN], cur = 0;
int dep[MAXN];
int l[MAXN], r[MAXN];
vector<int> e;
void dfs(int node, int prv, int ohno) {
  tin[node] = ++cur;
  dep[node] = ohno;
  e.push_back(node);
  for(auto x: adj[node]) {
    if(x.first != prv) {
      dfs(x.first, node, ohno + x.second);
      e.push_back(node);
    }
  }
  tout[node] = ++cur;
}

int lca_dep(int x, int y) {
  int m1 = min(l[x], l[y]), m2 = max(r[x], r[y]);
  int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
  return min(st[k][m1], st[k][m2 - (1<<k) + 1]).first;
}

int dist(int x, int y) {
  return dep[x] + dep[y] - 2 * lca_dep(x, y);
}

int lca_idx(int x, int y) {
  int m1 = min(l[x], l[y]), m2 = max(r[x], r[y]);
  int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
  return min(st[k][m1], st[k][m2 - (1<<k) + 1]).second;
}


int miS[MAXN], miT[MAXN];

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
  for(int i=0; i<N; i++) {
    miS[i] = miT[i] = 1e18;
  }
  for(int i=0; i<N-1; i++) {
    adj[A[i]].push_back({B[i], D[i]});
    adj[B[i]].push_back({A[i], D[i]});
  }
  dfs(0, -1, 0);
  for(int i=0; i<e.size(); i++) {
    r[e[i]] = i;
  }
  for(int i=e.size()-1; i>=0; i--) {
    l[e[i]] = i;
  }
  for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
  for(int i=1; i<20; i++) {
    for(int j=0; j<e.size(); j++) {
      if(j + (1<<i) - 1 < e.size()) {
        st[i][j] = min(st[i-1][j], st[i-1][j + (1<<(i-1))]);
      }
    }
  }
}

bool dfs_order(int a, int b) {
  return tin[a] < tin[b];
}

vector<int> adj2[MAXN]; 

char grp[MAXN]; 

int dpf(int node, int prv) {
  int ans = 1e18;
  for(int x: adj2[node]) {
    if(x != prv) {
      ans = min(ans, dpf(x, node));
      miS[node] = min(miS[node], miS[x]);
      miT[node] = min(miT[node], miT[x]);
    }
  }
  if(grp[node] == 'S') {
    miS[node] = dep[node];
  }
  else if(grp[node] == 'T') {
    miT[node] = dep[node];
  }
  ans = min(ans, miS[node] + miT[node] - 2 * dep[node]);
  return ans;
}

long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
  vector<int> v;
  for(int i=0; i<S; i++) {
    v.push_back(X[i]);
    grp[X[i]] = 'S';
  }
  for(int i=0; i<T; i++) {
    v.push_back(Y[i]);
    grp[Y[i]] = 'T';
  }
  sort(v.begin(), v.end(), dfs_order);
  unordered_map<int, int> here;
  for(int x: v) here[x] = 1;
  int V = v.size();
  for(int i=1; i<V; i++) {
    int lol = lca_idx(v[i], v[i-1]);
    if(!here[lol]) {
      here[lol] = 1;
      v.push_back(lol);
      grp[lol] = 'L';
    }
  }
  sort(v.begin(), v.end(), dfs_order);
  stack<int> st;
  for(int x: v) {
    adj2[x].clear();
    miS[x] = miT[x] = 1e18;
  }
  int rt;
  for(int x: v) {
    while(st.size() && !(tin[st.top()] < tin[x] && tout[x] < tout[st.top()])) {
      st.pop();
    }
    if(st.size()) {
      adj2[st.top()].push_back(x);
    }
    else {
      rt = x;
    }
    st.push(x);
  }
  return dpf(rt, -1);
}

Compilation message

factories.cpp: In function 'void Init(int32_t, int32_t*, int32_t*, int32_t*)':
factories.cpp:64:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0; i<e.size(); i++) {
      |                ~^~~~~~~~~
factories.cpp:70:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
      |                ~^~~~~~~~~
factories.cpp:72:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int j=0; j<e.size(); j++) {
      |                  ~^~~~~~~~~
factories.cpp:73:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |       if(j + (1<<i) - 1 < e.size()) {
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~
factories.cpp: In function 'long long int Query(int32_t, int32_t*, int32_t, int32_t*)':
factories.cpp:148:13: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |   return dpf(rt, -1);
      |          ~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24396 KB Output is correct
2 Correct 955 ms 34796 KB Output is correct
3 Correct 1094 ms 34788 KB Output is correct
4 Correct 993 ms 44512 KB Output is correct
5 Correct 864 ms 44584 KB Output is correct
6 Correct 757 ms 44232 KB Output is correct
7 Correct 1012 ms 44248 KB Output is correct
8 Correct 922 ms 44416 KB Output is correct
9 Correct 814 ms 44588 KB Output is correct
10 Correct 769 ms 44336 KB Output is correct
11 Correct 1041 ms 44164 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24140 KB Output is correct
2 Correct 1465 ms 394908 KB Output is correct
3 Correct 1492 ms 398332 KB Output is correct
4 Correct 997 ms 392464 KB Output is correct
5 Correct 1370 ms 433576 KB Output is correct
6 Correct 1592 ms 399612 KB Output is correct
7 Correct 1528 ms 100024 KB Output is correct
8 Correct 850 ms 99660 KB Output is correct
9 Correct 897 ms 106496 KB Output is correct
10 Correct 1503 ms 101216 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24396 KB Output is correct
2 Correct 955 ms 34796 KB Output is correct
3 Correct 1094 ms 34788 KB Output is correct
4 Correct 993 ms 44512 KB Output is correct
5 Correct 864 ms 44584 KB Output is correct
6 Correct 757 ms 44232 KB Output is correct
7 Correct 1012 ms 44248 KB Output is correct
8 Correct 922 ms 44416 KB Output is correct
9 Correct 814 ms 44588 KB Output is correct
10 Correct 769 ms 44336 KB Output is correct
11 Correct 1041 ms 44164 KB Output is correct
12 Correct 14 ms 24140 KB Output is correct
13 Correct 1465 ms 394908 KB Output is correct
14 Correct 1492 ms 398332 KB Output is correct
15 Correct 997 ms 392464 KB Output is correct
16 Correct 1370 ms 433576 KB Output is correct
17 Correct 1592 ms 399612 KB Output is correct
18 Correct 1528 ms 100024 KB Output is correct
19 Correct 850 ms 99660 KB Output is correct
20 Correct 897 ms 106496 KB Output is correct
21 Correct 1503 ms 101216 KB Output is correct
22 Correct 2653 ms 433064 KB Output is correct
23 Correct 2547 ms 431920 KB Output is correct
24 Correct 3614 ms 436408 KB Output is correct
25 Correct 3357 ms 441884 KB Output is correct
26 Correct 3095 ms 426548 KB Output is correct
27 Correct 2776 ms 464008 KB Output is correct
28 Correct 1939 ms 428008 KB Output is correct
29 Correct 2904 ms 425472 KB Output is correct
30 Correct 2870 ms 425300 KB Output is correct
31 Correct 2819 ms 425244 KB Output is correct
32 Correct 1353 ms 126512 KB Output is correct
33 Correct 1152 ms 120920 KB Output is correct
34 Correct 1545 ms 113020 KB Output is correct
35 Correct 1572 ms 112700 KB Output is correct
36 Correct 1875 ms 113372 KB Output is correct
37 Correct 1845 ms 113384 KB Output is correct