Submission #413446

#	Time	Username	Problem	Language	Result	Execution time	Memory
413446		souvenir_vayne	Factories (JOI14_factories)	C++14	100 / 100	5290 ms	368152 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
const long long N = 5e5 + 5, INF = 1e18 + 5;
 
long long n, cnt[N], mina[N], ans;
bool blocked[N];
 
struct Edge{
    long long b, w;
};
 
vector<Edge> tree[N];
vector<Edge> parent[N];
 
void subtreecnt(int v, int p){
    cnt[v] = 1;
 
    for(auto e : tree[v]){
        if(e.b != p && !blocked[e.b]){
            subtreecnt(e.b, v);
            cnt[v] += cnt[e.b];
        }
    }
}
 
int findcentroid(int v, int p, int root){
    for(auto e : tree[v]){
        if(e.b != p && !blocked[e.b] && cnt[e.b] > cnt[root] / 2){
            return findcentroid(e.b, v, root);
        }
    }
    return v;
}
 
void findpaths(int v, int p, int centroid, long long curw){
    parent[v].push_back({centroid, curw});
 
    for(auto e : tree[v]){
        if(e.b != p && !blocked[e.b]) findpaths(e.b, v, centroid, curw + e.w);
    }
}
 
void decomp(int v){
    subtreecnt(v, -1);
 
    int centroid = findcentroid(v, -1, v);
 
    findpaths(centroid, -1, centroid, 0);
 
    blocked[centroid] = true;
 
    for(auto e : tree[centroid]) if(!blocked[e.b]) decomp(e.b);
}
 
void Init(int n, int a[], int b[], int d[]){
    for(int i = 0; i < n - 1; i++){
        tree[a[i]].push_back({b[i], d[i]});
        tree[b[i]].push_back({a[i], d[i]});
    }
 
    decomp(0);
 
 
    fill(mina, mina + N, INF);
}
 
long long Query(int s, int x[], int t, int y[]){
    ans = INF;
 
    for(int i = 0; i < s; i++){
        for(auto e : parent[x[i]]){
            mina[e.b] = min(mina[e.b], e.w);
        }
    }
 
    for(int i = 0; i < t; i++){
        for(auto e : parent[y[i]]){
            ans = min(ans, mina[e.b] + e.w);
        }
    }
 
    for(int i = 0; i < s; i++){
        for(auto e : parent[x[i]]){
            mina[e.b] = INF;
        }
    }
 
    return ans;
}

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