제출 #284932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284932		BeanZ	공장들 (JOI14_factories)	C++14	15 / 100	8105 ms	151100 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"


using namespace std;

#define ll int
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lg = 20;
vector<pair<ll, ll>> node[N];
vector<ll> adj[N];
ll dp[N][21], dep[N];
long long dis[N];
ll sz[N];
ll par[N];
long long ans[N];
ll a[N];
bool ok[N], in[N];
void dfs(ll u, ll p){
        for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
        for (auto j : node[u]){
                if (j.first == p) continue;
                dp[j.first][0] = u;
                dis[j.first] = dis[u] + j.second;
                dep[j.first] = dep[u] + 1;
                dfs(j.first, u);
        }
}
ll findnewCT(ll u, ll p, ll S){
        for (auto j : adj[u]){
                if (j == p || in[j]) continue;
                if ((sz[j] * 2) >= S) return findnewCT(j, u, S);
        }
        return u;
}
void initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : adj[u]){
                if (j == p || in[j]) continue;
                initsz(j, u);
                sz[u] += sz[j];
        }
}
ll findCT(ll u, ll S){
        initsz(u, u);
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : adj[u]){
                if (in[j]) continue;
                if (sz[j] > sz[u]){
                        ll x = findCT(j, S - sz[u]);
                        par[x] = u;
                } else {
                        ll x = findCT(j, sz[j]);
                        par[x] = u;
                }
        }
        return u;
}
ll LCA(ll u, ll v){
        if (dep[u] > dep[v]) swap(u, v);
        ll dist = dep[v] - dep[u];
        for (int i = lg; i >= 0; i--){
                if (dist & (1 << i)) v = dp[v][i];
        }
        if (u == v) return u;
        for (int i = lg; i >= 0; i--){
                if (dp[u][i] != dp[v][i]){
                        u = dp[u][i];
                        v = dp[v][i];
                }
        }
        return dp[u][0];
}
long long dist(ll u, ll v){
        ll lca = LCA(u, v);
        return dis[u] + dis[v] - 2 * dis[lca];
}
vector<ll> recover;
void upd(ll u, ll root){
        if (!ok[u]) recover.push_back(u), ok[u] = 1;
        if (u == 0) return;
        ans[u] = min(ans[u], dist(root, u));
        upd(par[u], root);
}
long long get(ll u, ll root){
        if (u == 0) return 1e16;
        return min(ans[u] + dist(u, root), get(par[u], root));
}
long long Query(int S, int X[], int T, int Y[]){
        recover.clear();
        for (int i = 1; i <= T; i++){
                upd(Y[i - 1] + 1, Y[i - 1] + 1);
        }
        long long res = 1e18;
        for (int i = 1; i <= S; i++){
                res = min(res, get(X[i - 1] + 1, X[i - 1] + 1));
        }
        for (auto j : recover) ans[j] = 1e18, ok[j] = 0;
        return res;
}
void Init(int n, int A[], int B[], int D[]){
        for (int i = 1; i < n; i++){
                node[A[i - 1] + 1].push_back({B[i - 1] + 1, D[i - 1]});
                node[B[i - 1] + 1].push_back({A[i - 1] + 1, D[i - 1]});
                adj[A[i - 1] + 1].push_back(B[i - 1] + 1);
                adj[B[i - 1] + 1].push_back(A[i - 1] + 1);
        }
        dfs(1, 1);
        ll root = findCT(1, n);
        for (int i = 1; i <= n; i++) ans[i] = 1e18;
}
/*
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }

}
*/
/*
*/

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:112:12: warning: unused variable 'root' [-Wunused-variable]
  112 |         ll root = findCT(1, n);
      |            ^~~~

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