Submission #109205

#	Time	Username	Problem	Language	Result	Execution time	Memory
109205		thebes	Factories (JOI14_factories)	C++14	100 / 100	5390 ms	216232 KiB

factories

#include <bits/stdc++.h>
using namespace std;

const int MN = 5e5+5, LG = 20;
typedef long long ll;
ll N, i, j, anc[MN][LG], st[MN], en[MN], t, a[MN], b[MN], d[MN], dep[MN], col[MN];
vector<ll> vec;
vector<pair<ll,ll>> adj[MN];
void dfs(int n,int p,int dp){
    anc[n][0] = p; dep[n] = dp; st[n] = ++t;
    for(auto v : adj[n]){
        if(v.first==p) continue;
        d[v.first] = d[n]+v.second;
        dfs(v.first, n, dp+1);
    }
    en[n] = t;
}
void Init(int n,int *A,int *B,int *C){
    N = n;
    for(int i=0;i<n-1;i++){
        adj[A[i]].push_back({B[i],C[i]});
        adj[B[i]].push_back({A[i],C[i]});
    }
    dfs(0, -1, 1);
    for(int j=1;j<LG;j++){
        for(int i=0;i<N;i++){
            if(anc[i][j-1]!=-1)
                anc[i][j]=anc[anc[i][j-1]][j-1];
        }
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LG-1;i>=0;i--){
        if((1<<i)<=dep[x]-dep[y])
            x = anc[x][i];
    }
    if(x==y) return x;
    for(int i=LG-1;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}
bool cmp(int i,int j){return st[i]<st[j];}
ll Query(int S,int *X,int T,int *Y){
    ll ans = 1LL<<60;
    int *arr = (int*)malloc(sizeof(int)*(S+T));
    for(int i=0;i<S;i++) arr[i]=X[i];
    for(int i=0;i<T;i++) arr[i+S]=Y[i];
    sort(arr,arr+S+T,cmp);
    vec.clear();
    for(i=0;i<S+T-1;i++)
        vec.push_back(lca(arr[i],arr[i+1]));
    for(i=0;i<S+T;i++)
        vec.push_back(arr[i]);
    sort(vec.begin(),vec.end(),cmp);
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(auto v : vec) col[v] = -1;
    for(i=0;i<S;i++) col[X[i]]=0;
    for(i=0;i<T;i++) col[Y[i]]=1;
    stack<int> lst;
    for(auto v : vec){
        a[v] = b[v] = 1LL<<60;
        if(col[v]==0) a[v] = 0;
        else if(col[v]==1) b[v] = 0;
        while(lst.size()&&en[lst.top()]<st[v]){
            int n = lst.top();
            ans = min(ans, a[n]+b[n]);
            lst.pop();
            if(lst.size()){
                a[lst.top()]=min(a[lst.top()],a[n]+d[n]-d[lst.top()]);
                b[lst.top()]=min(b[lst.top()],b[n]+d[n]-d[lst.top()]);
            }
        }
        lst.push(v);
    }
    while(lst.size()){
        int n = lst.top();
        ans = min(ans, a[n]+b[n]);
        lst.pop();
        if(lst.size()){
            a[lst.top()]=min(a[lst.top()],a[n]+d[n]-d[lst.top()]);
            b[lst.top()]=min(b[lst.top()],b[n]+d[n]-d[lst.top()]);
        }
    }
    return ans;
}

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