Submission #373145

#	Time	Username	Problem	Language	Result	Execution time	Memory
373145		BartolM	Factories (JOI14_factories)	C++17	33 / 100	8074 ms	148712 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int MAXN=5e5+5;
const int LOG=20;
const int OFF=(1<<19);

struct Tournament{
    ll tour[2*OFF];
    Tournament() {
        fill(tour, tour+2*OFF, MAX);
    }
    ll query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
        if (lo>=a && hi<=b) return tour[pos];
        if (lo>=b || hi<=a) return MAX;
        int mid=(lo+hi)/2;
        return min(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
    }
    void update(int pos, ll val) {
        pos+=OFF; tour[pos]=val;
        pos/=2;
        while (pos) {
            tour[pos]=min(tour[pos*2], tour[pos*2+1]);
            pos/=2;
        }
    }
};

int n, dtime=0;
ll dist[MAXN];
int par[LOG][MAXN], dep[MAXN], L[MAXN], R[MAXN];
vector <pii> ls[MAXN];
ll da[MAXN], db[MAXN];
vector <int> v;

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

void dfs(int node, int rod, ll d) {
    par[0][node]=rod;
    dist[node]=d;
    dep[node]=dep[rod]+1;
    L[node]=dtime++;
//    printf("node: %d, dist: %lld, dep: %d, par: %d\n", node, dist[node], dep[node], rod);
    for (pii sus:ls[node]) if (sus.X!=rod) dfs(sus.X, node, d+sus.Y);
    R[node]=dtime;
}

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=0; j<n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
    }
    if (x==y) return x;
    for (int i=LOG-1; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

void rek(int node) {
    for (pii sus:ls[node]) {
        if (sus.X!=par[0][node]) {
            rek(sus.X);
            da[node]=min(da[node], da[sus.X]+sus.Y);
            db[node]=min(db[node], db[sus.X]+sus.Y);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=0; i<n-1; ++i) {
        ls[A[i]].pb(mp(B[i], D[i]));
        ls[B[i]].pb(mp(A[i], D[i]));
    }
    dfs(0, 0, 0);
    build();
}

Tournament TA, TB;

long long Query(int S, int x[], int T, int y[]) {
    v.clear();
    for (int i=0; i<S; ++i) {
        v.pb(x[i]);
        TA.update(L[x[i]], dist[x[i]]);
    }
    for (int i=0; i<T; ++i) {
        v.pb(y[i]);
        TB.update(L[y[i]], dist[y[i]]);
    }

    sort(v.begin(), v.end(), cmp);
    ll sol=MAX;
    for (int i=1; i<(int)v.size(); ++i) {
        int lc=lca(v[i-1], v[i]);
        ll curr=TA.query(L[lc], R[lc])+TB.query(L[lc], R[lc])-dist[lc]*2;
        sol=min(sol, curr);
    }
    for (int i=0; i<S; ++i) TA.update(L[x[i]], MAX);
    for (int i=0; i<T; ++i) TB.update(L[y[i]], MAX);
    return sol;
}

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