제출 #970859

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

factories

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

//#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//void setupIO(){
//    #define name "Whisper"
//    //Phu Trong from Nguyen Tat Thanh High School for gifted student
//    srand(time(NULL));
//    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//    freopen(name".inp", "r", stdin);
//    freopen(name".out", "w", stdout);
//    cout << fixed << setprecision(10);
//}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
const int MAX = 5e5 + 5;
int numNode, numQuery;


vector<int> to, from;

//Centroid Tree is used to solve this problem
//The max depth of the tree not exceed log(N)


struct Edge{
    int u, v, w;

    Edge(){}
    Edge(int _u, int _v, int _w){
        u = _u, v = _v, w = _w;
    }
    int other(int x){return (u ^ v ^ x);}
} edge[MAX];

vector<int> G[MAX];
long long sz[MAX], del[MAX], par[MAX], dist[MAX];
int reSubsize(int u, int p){
    sz[u] = 1;
    for (int&i : G[u]) {
        int v = edge[i].other(u);
        if(del[v]) continue;
        if(v ^ p){
            sz[u] += reSubsize(v, u);
        }
    }
    return sz[u];
}
int getCentroid(int u, int p, int siz){
    for (int& i : G[u]){
        int v = edge[i].other(u);
        if(v ^ p){
            if(!del[v] && 2 * sz[v] > siz) return getCentroid(v, u, siz);
        }
    }
    return u;
}
#define MIN_HIGH(u, v) (dep[u] < dep[v] ? (u) : (v))

long long dep[MAX], node[MAX << 1], st[MAX << 1][21], pos[MAX], D[MAX];
int cnt = 0;
void dfs(int u, int p = -1){
    node[++cnt] = u;
    pos[u] = cnt;
    for (int &i : G[u]){
        int v = edge[i].other(u);
        if(v ^ p){
            D[v] = D[u] + edge[i].w;
            dep[v] = dep[u] + 1;
            dfs(v, u);
            node[++cnt] = u;
        }
    }
}
int lca(int u, int v){
    int l = pos[u], r = pos[v];
    if (l > r) swap(l, r);

    int k = 31 - __builtin_clz(r - l + 1);
    return MIN_HIGH(st[l][k], st[r - (1 << k) + 1][k]);
}

long long F(int u, int v){
    return D[u] + D[v] - 2 * D[lca(u, v)];
}
void buildCT(int root, int p){
    root = getCentroid(root, p, reSubsize(root, p));
    del[root] = 1;
    par[root] = p;
    dist[root] = LINF;
    for (int&i : G[root]){
        int v = edge[i].other(root);
        if(del[v]) continue;
        if(v ^ p){
            buildCT(v, root);
        }
    }
}
void Init(int N, int A[], int B[], int D[]){
    numNode = N;
    for (int i = 0; i < numNode - 1; ++i){
        ++A[i], ++B[i];
        edge[i + 1] = Edge(A[i], B[i], D[i]);
        G[A[i]].emplace_back(i + 1);
        G[B[i]].emplace_back(i + 1);
    }
    dfs(1);

    for (int i = 1; i <= cnt; ++i) st[i][0] = node[i];
    for (int k = 1; MASK(k) <= cnt; ++k){
        for (int i = 1; i + MASK(k) - 1 <= cnt; ++i){
            st[i][k] = MIN_HIGH(st[i][k - 1], st[i + MASK(k - 1)][k - 1]);
        }
    }
    buildCT(1, -1);
}



long long Solve(){
    long long res = LINF;
    for (int i = 0; i < (int)from.size(); ++i){
        for (int cur = from[i] + 1; cur != -1; cur = par[cur]){
            minimize(dist[cur], F(cur, from[i] + 1));
        }
    }
    for (int i = 0; i < (int)to.size(); ++i){
        for (int cur = to[i] + 1; cur != -1; cur = par[cur]){
            minimize(res, dist[cur] + F(cur, to[i] + 1));
        }
    }
    for (int i = 0; i < (int)from.size(); ++i){
        for (int cur = from[i] + 1; cur != -1; cur = par[cur]){
            dist[cur] = LINF;
        }
    }
    return res;
}
long long Query(int S, int X[], int T, int Y[]){
    from.clear(); to.clear();
    FOR(i, 0, T - 1) from.push_back(Y[i]);
    FOR(i, 0, S - 1) to.push_back(X[i]);

    return Solve();
}

//int N, A[MAX], B[MAX], Di[MAX], Q;
//int X[MAX], Y[MAX];
//void Whisper(){
//    cin >> N >> Q;
//    for (int i = 0; i < N - 1; ++i){
//        cin >> A[i] >> B[i] >> Di[i];
//    }
//    Init(N, A, B, Di);
//    for (int i = 1; i <= Q; ++i){
//        int S, T; cin >> S >> T;
//        FOR(v, 0, S - 1) cin >> X[v];
//        FOR(v, 0, T - 1) cin >> Y[v];
//        cout << Query(S, X, T, Y) << '\n';
//    }
//}
//
//
//signed main(){
//    setupIO();
//    int Test = 1;
////    cin >> Test;
//    for ( int i = 1 ; i <= Test ; i++ ){
//        Whisper();
//        if (i < Test) cout << '\n';
//    }
//}

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