Submission #629009

#	Time	Username	Problem	Language	Result	Execution time	Memory
629009		X_Ray	Factories (JOI14_factories)	C++14	100 / 100	4804 ms	195408 KiB

factories

#include <bits/stdc++.h>
//#pragma GCC optimize ("O2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("strict-overflow")
//#pragma GCC target("avx,avx2,fma")
//#pragma comment(linker, "/STACK:268435456");
#define pb push_back
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll inf = 1e16;
bool blocked[500001];
int n, children[500001], par[500001], cnt[500001], uniRoot;
ll ans = 1e16, dis[500001][19];
vector<pair<int, int>> adj[500001];
gp_hash_table<int, ll> minDis;
void DFS(int u, int prv){
    children[u] = 1;
    for(auto& i: adj[u]){
        if(blocked[i.first] || i.first == prv) continue;
        DFS(i.first, u);
        children[u] += children[i.first];
    }
}
int secDFS(int u, int prv){
    bool flag = 1;
    for(auto& i: adj[u]) if(! blocked[i.first] && children[i.first]*2 > children[u]) flag = 0;
    if(flag) return u;
    int anc = -1;
    for(auto& i: adj[u]){
        if(i.first == prv || blocked[i.first]) continue;
        children[u] -= children[i.first];
        children[i.first] += children[u];
        if(anc == -1) anc = secDFS(i.first, u);
        children[i.first] -= children[u];
        children[u] += children[i.first];
    }
    return anc;
}
void distDFS(int u, int prv, ll curDis, int root){
    dis[u][cnt[u]++] = curDis;
    for(auto& i: adj[u]){
        if(blocked[i.first] || i.first == prv) continue;
        distDFS(i.first, u, curDis+i.second, root);
    }
}
int decompose(int u){
    DFS(u, -1);
    int root = secDFS(u, -1);
    distDFS(root, -1, 0, root);
    blocked[root] = 1;
    for(auto& i: adj[root]) {
        if(blocked[i.first]) continue;
        int nextRoot = decompose(i.first);
        par[nextRoot] = root;
    }
    return root;
}
void Init(int N, int A[], int B[], int C[]) {
    n = N;
    for(int i = 0; i < N-1; i++){
        adj[A[i]].pb(mp(B[i], C[i]));
        adj[B[i]].pb(mp(A[i], C[i]));
    }
    uniRoot = decompose(0);
    par[uniRoot] = -1;
}
ll Query(int S, int X[], int T, int Y[]){
    //The answer is the lowest LCA for a pair {X_i, Y_j} in the Centroid Tree
    //O(STlogN) Naive
    //How do we process queries in O((S+T)) or O((S+T)logN)?
    //Idea: for all S, update the shortest distance for all nodes between the root of the centroid tree and X_i, and for Y_i, move up the centroid tree and update the answer for each node.
    //The height of the centroid tree is O(logN), so we get O((S+T)logN)
    //We can use Euler Tour Trick to get distances in O(1)
    //Alternatively just store the distances
    ans = inf;
    minDis.clear();
    for(int i = 0; i < S; i++){
        int cur = X[i], curcnt = cnt[X[i]]-1;
        while(cur != -1){
            if(minDis.find(cur) == minDis.end()) minDis[cur] = inf;
            minDis[cur] = min(minDis[cur], dis[X[i]][curcnt--]);
            cur = par[cur];
        }
    }
    for(int i = 0; i < T; i++){
        int cur = Y[i], curcnt = cnt[Y[i]]-1;
        while(cur != -1){
            if(minDis.find(cur) != minDis.end()) ans = min(ans, minDis[cur]+dis[Y[i]][curcnt]);
            curcnt--;
            cur = par[cur];
        }
    }
    assert(ans != 0);
    return ans;
}
/*
int main() {
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    int A[6] = {0, 1, 2, 2, 4, 1}, B[6] = {1, 2, 3, 4, 5, 6}, C[6] = {4, 4, 5, 6, 5, 3};
    Init(7, A, B, C);
    int X1[2] = {0, 6}, Y1[2] = {3, 4};
    cout << Query(2, X1, 2, Y1) << "\n";
    int X2[3] = {0, 1, 3}, Y2[2] = {4, 6};
    cout << Query(3, X2, 2, Y2) << "\n";
    int X3[1] = {2}, Y3[1] = {5};
    cout << Query(1, X3, 1, Y3) << "\n";
}
*/

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