Submission #656606

#	Time	Username	Problem	Language	Result	Execution time	Memory
656606		socpite	Factories (JOI14_factories)	C++14	100 / 100	2691 ms	205736 KiB

factories

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

#define f first
#define s second

typedef long long ll;

const int maxn = 5e5+5;
const ll inf = 1e18;

vector<pair<int, int>> tree[maxn];
vector<int> graph[maxn];
int crr;
int st[20][2*maxn];
int lg[2*maxn], L[maxn], R[maxn];
int mm[2][maxn];
ll dp[2][maxn];
ll d1[maxn], d2[maxn];
ll ans;
int mn(int a, int b){
    return d1[a] < d1[b] ? a : b;
}

bool cmp(int a, int b){return L[a] < L[b];}

bool insub(int a, int b){
    return L[b] <= L[a] && R[b] >= L[a];
}

void pre_dfs(int x, int p = -1){
    st[0][++crr]=x;
    L[x]=crr;
    d1[x]=d1[p]+1;
    for(auto v: tree[x]){
        if(v.f == p)continue;
        d2[v.f]=d2[x]+v.s;
        pre_dfs(v.f, x);
        st[0][++crr]=x;
    }
    R[x] = crr;
}

void build(){
    for(int i = 2; i <= crr; i++)lg[i] = lg[i>>1]+1;
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= crr; j++){
            if(j+(1<<i)-1 > crr)break;
            st[i][j] = mn(st[i-1][j], st[i-1][j+(1<<(i-1))]);
        }
    }
}

int LCA(int a, int b){
    //cout << a << " " << b << endl;
    int l = min(L[a], L[b]), r = max(R[a], R[b]), d = lg[r-l+1];
    return mn(st[d][l], st[d][r-(1<<d)+1]);
}

void dfs(int x){
    if(mm[0][x])dp[0][x]=0;
    if(mm[1][x])dp[1][x]=0;
    //cout << x << " " << dp[0][x] << " " << dp[1][x] << endl;
    for(auto v: graph[x]){
        dfs(v);
        dp[0][x] = min(dp[0][v]+d2[v]-d2[x], dp[0][x]);
        dp[1][x] = min(dp[1][v]+d2[v]-d2[x], dp[1][x]);
    }
    ans = min(ans, dp[0][x] + dp[1][x]);
}

void Init(int N, int A[], int B[], int D[]) {
    crr = 0;
    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]});
    }
    pre_dfs(1);
    build();
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> nd;
    ans = inf;
    for(int i = 0; i < S; i++){
        nd.push_back(X[i]);
        mm[0][X[i]]=1;
    }
    for(int i = 0; i < T; i++){
        nd.push_back(Y[i]);
        mm[1][Y[i]]=1;
    }
    sort(nd.begin(), nd.end(), cmp);
    for(int i = 0; i < S+T-1; i++){
        nd.push_back(LCA(nd[i], nd[i+1]));
    }
    sort(nd.begin(), nd.end(), cmp);
    nd.erase(unique(nd.begin(), nd.end()), nd.end());
    stack<int> stk;
    for(auto v: nd){
      dp[0][v]=dp[1][v]=inf;
    }
    stk.push(nd[0]);
    for(int i = 1; i < nd.size(); i++){
        while(!insub(nd[i], stk.top()))stk.pop();
        graph[stk.top()].push_back(nd[i]);
        stk.push(nd[i]);
    }
    dfs(nd[0]);
    for(auto v: nd){
        mm[0][v]=mm[1][v]=0;
        graph[v].clear();
    }
    return ans;
}
                

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 1; i < nd.size(); i++){
      |                    ~~^~~~~~~~~~~

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