oj.uz

Submission #656635

# Submission time Handle Problem Language Result Execution time Memory
656635 2022-11-08T02:46:37 Z uylulu Factories (JOI14_factories) C++17
100 / 100
 4794 ms 301760 KB 
#include "factories.h"
#include<bits/stdc++.h>

#define ll long long


using namespace std;

const ll N = 5e5 + 5,K = 23,oo = 1e17;

vector<pair<ll,ll>> adj[N + 1];
ll dis[N + 1],fi[N + 1],t = 0;

ll eu[2*N + 1],sparse[2*N + 1][K + 1];


void dfs(ll s,ll pa) {
  fi[s] = t;
  eu[t] = s;
  t++;
  for(auto u : adj[s]) {
    if(u.first == pa) continue;

    dis[u.first] = dis[s] + u.second;
    dfs(u.first,s);

    eu[t] = s;
    t++;
  }
}

ll lg[2*N + 1];

void build() {
  for(ll i = 2;i <= t;i++) {
    lg[i] = lg[i/2] + 1;
  }

  for(ll i = 0;i < t;i++) {
    sparse[i][0] = dis[eu[i]];
  } 
  for(ll j = 1;j <= K;j++) {
    for(ll i = 0;i + (1<<j) <= t;i++) {
      sparse[i][j] = min(sparse[i][j - 1],sparse[i + (1<<(j - 1))][j - 1]);
    }
  }
}

ll query(ll l,ll r) {
  if(l > r) swap(l,r);

  ll len = lg[r - l + 1];
  return min(sparse[l][len],sparse[r - (1<<len) + 1][len]);
}

ll lca(ll a,ll b) {
  return query(fi[a],fi[b]);
}

ll help_dis(ll a,ll b) {
  return dis[a] + dis[b] - 2*lca(a,b);
}

ll cha[N + 1],sz[N + 1];
bool dele[N + 1];

void init(ll s,ll pa) {
  sz[s] = 1;
  for(auto u : adj[s]) {
    if(u.first == pa || dele[u.first]) continue;

    init(u.first,s);

    sz[s] += sz[u.first];
  }
}

ll find_cen(ll s,ll cnt,ll pa) {
  for(auto u : adj[s]) {
    if(dele[u.first] || u.first == pa) continue;

    if(sz[u.first]*2 > cnt) {
      return find_cen(u.first,cnt,s);
    }
  }
  return s;
}

void decompose(ll s,ll pa) {
  init(s,-1);
  ll u = find_cen(s,sz[s],pa);
  dele[u] = true;

  cha[u] = pa;

  for(auto v : adj[u]) {
    if(dele[v.first]) continue;
    decompose(v.first,u);
  }
}

ll dp[N + 1];

void Init(int len, int A[], int B[], int D[]) {
  int n = len;
  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]});
  }

  for(int i = 0;i < n;i++) {
    fi[i] = oo;
    dp[i] = oo;
  }
  dfs(0,-1);
  build();
  decompose(0,-1);
  
}


long long Query(int s, int x[], int t, int y[]) {


  for(ll i = 0;i < s;i++) {
    ll crr = x[i];

    while(crr != -1) {
      dp[crr] = min(dp[crr],help_dis(crr,x[i]));
      crr = cha[crr];
    }
    // cout<<endl;
  }

  ll res = oo;

  for(int i = 0;i < t;i++) {
    int crr = y[i];

    while(crr != -1) {
      res = min(res,dp[crr] + help_dis(crr,y[i]));
      crr = cha[crr];
      // cout<<crr<<" "<<dp[crr]<<" ";
    }
    // cout<<endl;
  }

  for(ll i = 0;i < s;i++) {
    ll crr = x[i];

    while(crr != -1) {
      dp[crr] = oo;
      crr = cha[crr];
    }
  }

  return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12652 KB Output is correct
2 Correct 357 ms 22576 KB Output is correct
3 Correct 494 ms 22616 KB Output is correct
4 Correct 442 ms 22764 KB Output is correct
5 Correct 577 ms 22980 KB Output is correct
6 Correct 240 ms 22580 KB Output is correct
7 Correct 441 ms 22644 KB Output is correct
8 Correct 414 ms 22660 KB Output is correct
9 Correct 479 ms 22916 KB Output is correct
10 Correct 261 ms 22616 KB Output is correct
11 Correct 440 ms 22672 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2247 ms 274084 KB Output is correct
3 Correct 3281 ms 276956 KB Output is correct
4 Correct 1076 ms 271760 KB Output is correct
5 Correct 4119 ms 301760 KB Output is correct
6 Correct 3199 ms 278376 KB Output is correct
7 Correct 1629 ms 73156 KB Output is correct
8 Correct 604 ms 72976 KB Output is correct
9 Correct 2098 ms 77072 KB Output is correct
10 Correct 1758 ms 74396 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12652 KB Output is correct
2 Correct 357 ms 22576 KB Output is correct
3 Correct 494 ms 22616 KB Output is correct
4 Correct 442 ms 22764 KB Output is correct
5 Correct 577 ms 22980 KB Output is correct
6 Correct 240 ms 22580 KB Output is correct
7 Correct 441 ms 22644 KB Output is correct
8 Correct 414 ms 22660 KB Output is correct
9 Correct 479 ms 22916 KB Output is correct
10 Correct 261 ms 22616 KB Output is correct
11 Correct 440 ms 22672 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2247 ms 274084 KB Output is correct
14 Correct 3281 ms 276956 KB Output is correct
15 Correct 1076 ms 271760 KB Output is correct
16 Correct 4119 ms 301760 KB Output is correct
17 Correct 3199 ms 278376 KB Output is correct
18 Correct 1629 ms 73156 KB Output is correct
19 Correct 604 ms 72976 KB Output is correct
20 Correct 2098 ms 77072 KB Output is correct
21 Correct 1758 ms 74396 KB Output is correct
22 Correct 3421 ms 275640 KB Output is correct
23 Correct 3412 ms 277940 KB Output is correct
24 Correct 4508 ms 278972 KB Output is correct
25 Correct 4289 ms 282504 KB Output is correct
26 Correct 4386 ms 279088 KB Output is correct
27 Correct 4794 ms 299756 KB Output is correct
28 Correct 1137 ms 275708 KB Output is correct
29 Correct 3790 ms 278704 KB Output is correct
30 Correct 4051 ms 278168 KB Output is correct
31 Correct 3899 ms 278808 KB Output is correct
32 Correct 1530 ms 78028 KB Output is correct
33 Correct 485 ms 73368 KB Output is correct
34 Correct 1018 ms 70988 KB Output is correct
35 Correct 1064 ms 71140 KB Output is correct
36 Correct 1391 ms 71932 KB Output is correct
37 Correct 1360 ms 71832 KB Output is correct