Submission #372596

#	Time	Username	Problem	Language	Result	Execution time	Memory
372596		erfanmir	Factories (JOI14_factories)	C++17	0 / 100	123 ms	96364 KiB

factories

// In the name of god

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

using namespace std;

  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair

const int MAXN = 1e6 + 10;
const int MAXLG = 20;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 1e18;

int n, par[MAXN][MAXLG], h[MAXN], st[MAXN], ft[MAXN], cnt = 1, r[MAXN], b[MAXN], stk[MAXN];
vector<int> g[MAXN];
vector<pii> adj[MAXN];
ll dp[MAXN], rd[MAXN], bd[MAXN];

//int A1[MAXN], B1[MAXN], D1[MAXN], X1[MAXN], Y1[MAXN], S1, T1, q;

void dfs(int v = 1){
    st[v] = cnt++;
    for(auto u : adj[v]){
        if(u.F == par[v][0]){
            continue;
        }
        h[u.F] = h[v] + 1;
        dp[u.F] = dp[v] + u.S;
        par[u.F][0] = v;
        dfs(u.F);
    }
    ft[v] = cnt;
}

int edq(int u, int val){
    for(int i = 0; i < MAXLG; i++){
        if(val & 1){
            u = par[u][i];
        }
        val /= 2;
    }
    return u;
}

int lca(int v, int u){
    if(h[v] > h[u]){
        swap(v, u);
    }
    u = edq(u, h[u] - h[v]);
    if(v == u){
        return v;
    }
    for(int i = MAXLG - 1; ~i; i--){
        if(par[v][i] == par[u][i]){
            continue;
        }
        v = par[v][i];
        u = par[u][i];
    }
    return par[v][0];
}

bool cmp(int A, int B){
    return st[A] < st[B];
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i = 0; i < n - 1; i++){
        adj[A[i] + 1].push_back(mp(B[i] + 1, D[i]));
        adj[B[i] + 1].push_back(mp(A[i] + 1, D[i]));
    }
    dfs();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < MAXLG; j++){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
}

void sfd(int v){
    rd[v] = bd[v] = INF;
    if(b[v]){
        bd[v] = 0;
    }
    if(r[v]){
        rd[v] = 0;
    }
    for(auto u : g[v]){
        sfd(u);
        bd[v] = min(bd[v], bd[u] - dp[v] + dp[u]);
        rd[v] = min(rd[v], rd[u] - dp[v] + dp[u]);
    }
}

ll Query(int S, int X[], int T, int Y[]){
    ll ans = INF;
    vector<int> vec;

    for(int i = 0; i < S; i++){
        vec.push_back(X[i] + 1);
        b[X[i] + 1] = 1;
    }
    for(int i = 0; i < T; i++){
        vec.push_back(Y[i] + 1);
        r[Y[i] + 1] = 1;
    }
    sort(all(vec), cmp);
    for(int i = 0; i < S + T - 1; i++){
        vec.push_back(lca(vec[i], vec[i + 1]));
    }
    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());

    int ptr = 0;
    stk[++ptr] = vec[0];
    for(int i = 1; i < (int)vec.size(); i++){
        while(st[stk[ptr]] > st[vec[i]] || ft[vec[i]] > ft[stk[ptr]]){
            stk[ptr] = 0;
            ptr--;
        }
        g[stk[ptr]].push_back(vec[i]);
        stk[++ptr] = vec[i];
    }
    sfd(vec[0]);
    for(auto v : vec){
        g[v].clear();
        ans = min(ans, bd[v] + rd[v]);
        b[v] = r[v] = 0;
    }
    return ans;
}

/*int main(){
    scanf("%d %d", &n, &q);
    for(int i = 0; i < n - 1; i++){
        scanf("%d %d %d", A1 + i, B1 + i, D1 + i);
    }
    Init(n, A1, B1, D1);
    while(q--){
        scanf("%d %d", &S1, &T1);
        for(int i = 0; i < S1; i++){
            scanf("%d", X1 + i);
        }
        for(int i = 0; i < T1; i++){
            scanf("%d", Y1 +  i);
        }
        printf("%lld\n", Query(S1, X1, T1, Y1));
    }
}*/

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