Submission #285080

#	Time	Username	Problem	Language	Result	Execution time	Memory
285080		BeanZ	Factories (JOI14_factories)	C++14	100 / 100	7380 ms	241356 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 = 19;
vector<pair<ll, ll>> node[N];
ll dep[N], tin[N];
long long dis[N];
ll sz[N];
ll par[N], st[N];
long long ans[N];
bool ok[N], in[N];
ll timer = 0;
pair<ll, ll> dp[20][N * 2];
void dfs(ll u, ll p){
        st[u] = ++timer;
        tin[timer] = u;
        for (auto j : node[u]){
                if (j.first == p) continue;
                dis[j.first] = dis[u] + j.second;
                dep[j.first] = dep[u] + 1;
                dfs(j.first, u);
                tin[++timer] = u;
        }
}
void buildLCA(){
        for (int i = 1; i <= timer; i++) dp[0][i] = {dep[tin[i]], tin[i]};
        for (int i = 1; i <= lg; i++){
                for (int j = 1; j <= timer; j++){
                        if ((j + (1 << i)) > timer) break;
                        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
                }
        }
}
ll findnewCT(ll u, ll p, ll S){
        for (auto j : node[u]){
                if (j.first == p || in[j.first]) continue;
                if ((sz[j.first] * 2) > S) return findnewCT(j.first, u, S);
        }
        return u;
}
ll initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : node[u]){
                if (j.first == p || in[j.first]) continue;
                sz[u] += initsz(j.first, u);;
        }
        return sz[u];
}
ll findCT(ll u){
        ll S = initsz(u, u);
        u = findnewCT(u, u, S);
        in[u] = 1;
        for (auto j : node[u]){
                if (in[j.first]) continue;
                par[findCT(j.first)] = u;
        }
        return u;
}
ll LCA(ll u, ll v){
        ll l = st[u], r = st[v];
        if (l > r) swap(l, r);
        ll k = 31 - __builtin_clz(r - l + 1);
        return min(dp[k][l], dp[k][r - (1 << k) + 1]).second;
}
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 1e15;
        return min(ans[u] + dist(u, root), get(par[u], root));
}
long long Query(int S, int X[], int T, int Y[]){
        //recover.clear();
        if (S > T){
                for (int i = 1; i <= T; i++){
                        upd(Y[i - 1] + 1, Y[i - 1] + 1);
                }
                long long res = 1e15;
                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;
                for (int i = 1; i <= T; i++){
                        ll now = Y[i - 1] + 1;
                        while (now){
                                ans[now] = 1e15;
                                now = par[now];
                        }
                }
                return res;
        } else {
                for (int i = 1; i <= S; i++){
                        upd(X[i - 1] + 1, X[i - 1] + 1);
                }
                long long res = 1e15;
                for (int i = 1; i <= T; i++){
                        res = min(res, get(Y[i - 1] + 1, Y[i - 1] + 1));
                }
                //for (auto j : recover) ans[j] = 1e18, ok[j] = 0;
                for (int i = 1; i <= S; i++){
                        ll now = X[i - 1] + 1;
                        while (now){
                                ans[now] = 1e15;
                                now = par[now];
                        }
                }
                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]});
        }
        dfs(1, 1);
        buildLCA();
        ll root = findCT(1);
        for (int i = 1; i <= n; i++) ans[i] = 1e15;
}
/*
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);
        }
}
*/
/*
*/

Compilation message (stderr)

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

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