제출 #660389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660389		rafatoa	공장들 (JOI14_factories)	C++17	100 / 100	4326 ms	288600 KiB

factories

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
 
#define F first
// #define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define double ld
// #define int long long
const long long INF = 4e18;
 
const int MN = 5e5+1;
 
int n;
vpi adj[MN];
int st[2*MN][21];
long long saved[MN][21];
long long d[MN], dc[MN], sub[MN], par[MN], best[MN], vis[MN], tin[MN], eul[2*MN];
bool del[MN];
 
int tt = 0;
 
int lg2(int x){
    return 31-__builtin_clz(x);
}
 
int cmp(int a, int b){
    return (d[a] < d[b] ? a : b);
}
 
int lca(int a, int b){
    if(tin[a] > tin[b]) swap(a, b);
    int len = tin[b]-tin[a]+1, lg = lg2(len);
    return cmp(st[tin[a]][lg], st[tin[b]-(1LL<<lg)+1][lg]);
}
 
long long dist(int a, int b){
    return dc[a]+dc[b]-2*dc[lca(a, b)];
}
 
void build(){
    int time = 0;
    function<void(int, int)> dfs0 = [&](int s, int e){
        tin[s] = time;
        eul[time++] = s;
        for(auto [u, c]:adj[s]){
            if(u == e) continue;
            d[u] = d[s]+1;
            dc[u] = dc[s]+c;
            dfs0(u, s);
            eul[time++] = s;
        }
    };
    dfs0(1, 0);
 
    for(int i=0; i<2*n-1; i++) st[i][0] = eul[i];
    for(int j=1; j<=20; j++)
    for(int i=0; i+(1LL<<j)-1<2*n-1; i++)
        st[i][j] = cmp(st[i][j-1], st[i+(1LL<<(j-1))][j-1]);
 
    //START_CENTROID
 
    function<void(int, int)> dfs_sub = [&](int s, int e){
        sub[s] = 1;
        for(auto [u, c]:adj[s]){
            if(u == e || del[u]) continue;
            dfs_sub(u, s);
            sub[s] += sub[u];
        }
    };
 
    function<int(int, int, int)> centroid = [&](int s, int e, int sz){
        for(auto [u, c]:adj[s])
            if(u != e && !del[u] && sub[u] > sz/2) return centroid(u, s, sz);
        return s;
    };
 
    function<void(int, int)> decompose = [&](int s, int p){
        dfs_sub(s, 0);
        int C = centroid(s, 0, sub[s]);
        par[C] = p;
 
        del[C] = 1;
        for(auto [u, c]:adj[C])
            if(!del[u]) decompose(u, C);
    };
    decompose(1, -1);

    for(int i=1; i<=n; i++){
        int curr = i, c = 0;
        while(curr != -1){
            saved[i][c] = dist(i, curr);
            c++;
            curr = par[curr];
        }
    }
 
    //END_CENTROID
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=0; i<n-1; i++){
        adj[A[i]+1].pb({B[i]+1, D[i]});
        adj[B[i]+1].pb({A[i]+1, D[i]});
    }

    for(int i=0; i<MN; i++)
    for(int j=0; j<=20; j++)
        saved[i][j] = -1;
 
    build();
}
 
long long Query(int S, int X[], int T, int Y[]){
    tt++;
    long long ans = INF;
    
    for(int i=0; i<T; i++){
        Y[i]++;
        int curr = Y[i], c = 0;
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            best[curr] = min(best[curr], saved[Y[i]][c]);
            curr = par[curr];
            c++;
        }
    }

    for(int i=0; i<S; i++){
        X[i]++;
        int curr = X[i], c = 0;
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            ans = min(ans, best[curr]+saved[X[i]][c]);
            curr = par[curr];
            c++;
        }
    }
 
    return ans;
}

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