제출 #1128541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128541		KK_1729	공장들 (JOI14_factories)	C++17	33 / 100	8092 ms	135676 KiB

factories

#include <bits/stdc++.h>
using namespace std;
#include "factories.h"

// #define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
int min(int x, int y){
  if (x < y) return x;
  return y;
}
vector<vector<pair<int, int>>> graph;
vector<int> depth;
vector<vector<int>> up;
vector<int> ctree;
vector<int> subtree;
vector<int> vis(100000);
vector<long long> d;
vector<long long> ans;
int L = 0;
int C = 1;
 
int dp(int x, int p = -1){
    if (vis[x]) return 0;
    subtree[x] = 1;
    for (auto [node, w]: graph[x]){
        if (node == p) continue;
        subtree[x] += dp(node, x);
    }
    return subtree[x];
}
int find_centroid(int x, int p, int n){
    for (auto [node, w]: graph[x]){
        if (node == p) continue;
        if (!vis[node] && subtree[node]*2 > n) return find_centroid(node, x, n);
    }
    return x;
}
void init_centroid(int x = 1, int p = -1){
    dp(x);
    int c = find_centroid(x, -1, subtree[x]);
    vis[c] = 1;
    ctree[c] = p;
 
    for (auto [node, w]: graph[c]){
        if (!vis[node]){
            init_centroid(node, c);
        }
    }
}
int lca(int x, int y){
    if (depth[x] < depth[y]) swap(x, y);
    int k = depth[x]-depth[y];
    for (int i = L-1; i >= 0; i--){
        if (k & (1 << i)) x = up[x][i];
    }
    if (x == y) return x;
    for (int i = L-1; i >= 0; i--){
        if (up[x][i] != up[y][i]){
            x = up[x][i];
            y = up[y][i];
        }
    }
    
    return up[x][0];
}
long long dist(int x, int y){
    return d[x]+d[y]-(2ll)*d[lca(x, y)];
}
 
void update(int x, int t){
    int k = x;
    ans[x] = 0;
    while (k != -1){
        if (t == 0) ans[k] = min(ans[k], ans[x]+dist(x, k));
        else ans[k] = 1e16;
        k = ctree[k];
    }
}   
long long query(int x){
    long long e = 1e16;
    int k = x;
    while (k != -1){
        e = min(e, ans[k]+dist(x, k));
        k = ctree[k];
    }
    return e;
}





void Init(int N, int A[], int B[], int D[]) {
  int n = N;
    graph.resize(n+1);
    subtree.resize(n+1);
    ans.resize(n+1, 1e16);
    L = log2(n)+1;
    vis.resize(n+1);
    depth.resize(n+1);
    d.resize(n+1);
    ctree.resize(n+1);
    up.resize(n+1, vector<int>(L));

  FOR(i,0,n-1){
    graph[A[i]].pb({B[i], D[i]});
    graph[B[i]].pb({A[i], D[i]});
  }


  vector<int> visited(n+1);
  stack<int> s;
  s.push(0);
  while (!s.empty()){
    int current = s.top();
    s.pop();
    if (visited[current]) continue;
    for (auto x: graph[current]){
      if (visited[x.first]) continue;
      d[x.first] = d[current]+x.second;
      depth[x.first] = depth[current]+1;
      up[x.first][0] = current;
      s.push(x.first);
    }
    visited[current] = 1;
  }

    for (int i = 1; i < L; i++){
      for (int j = 1; j <= n; j++) up[j][i] = up[ up[j][i-1] ][i-1];
    }

    C = find_centroid(0, -1, n);
    init_centroid();


}

long long Query(int S, int X[], int T, int Y[]) {
  long long ANS = 1e16;
  FOR(i,0,S){
    update(X[i], 0);
  }
  FOR(i,0,T){
    ANS = min(ANS, query(Y[i]));
  }
  FOR(i,0,S){
    update(X[i], 1);
  }
  return ANS;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67