Submission #1230691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230691		quannnguyen2009	Factories (JOI14_factories)	C++20	0 / 100	17 ms	24132 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 5e5+5, mod = 1e9+7, inf = 1e18, L = 19;

int timer;
vector<ii> adj[N];
vector<ii> adj_[N];
int d[N], in[N], out[N];
int mn1[N], mn2[N], typ[N];
int up[N][L];

void dfs(int u, int p) {
    d[u] = d[p]+1;
    in[u] = ++timer;
    up[u][0] = p;
    for (int i=1; i<L; i++) up[u][i] = up[up[u][i-1]][i-1];
    for (auto [v, l]: adj[u]) {
        if (v!=p) dfs(v, u);
    }
    out[u] = timer;
}

int kth_ancestor(int u, int k) {
    for (int i=0; i<L; i++) {
        if(k>>i&1) u = up[u][i];
    }
    return u;
}

int lca(int u, int v) {
    if (d[u]!=d[v]) {
        if(d[u]>d[v]) swap(u, v);
        v = kth_ancestor(v, d[v]-d[u]);
    }
    if(u==v) return u;
    for (int i=L-1; i>=0; i--) {
        if (up[u][i]!=up[v][i]) {
            u = up[u][i]; v = up[v][i];
        }
    }
    return up[u][0];
}

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

bool cmp(int u, int v) {
    return in[u]<in[v];
}

bool is_par(int u, int v) {
    return (in[u]<=in[v] && out[v]<=out[u]);
}

int ans;

void dfs_solve(int u, int p) {
    if (typ[u]==1) mn1[u] = min(mn1[u], 0);
    else if (typ[u]==2) mn2[u] = min(mn2[u], 0);
    for (auto [v, l]: adj_[u]) {
        if (v!=p) {
            dfs_solve(v, u);
            mn1[u] = min(mn1[u], l+mn1[v]);
            mn2[u] = min(mn2[u], l+mn2[v]);
        }
    }
    ans = min(ans, mn1[u]+mn2[u]);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<min(2*(S+T), N); i++) {
        adj_[i].clear();
        mn1[i] = mn2[i] = inf;
        typ[i] = 0;
    }
    ans = inf;
    vector<int> v;
    for (int i=0; i<S; i++) {
        X[i]++;
        v.pb(X[i]);
    }
    for (int i=0; i<T; i++) {
        Y[i]++;
        v.pb(Y[i]);
    }
    sort(all(v), cmp);
    int tmp = sz(v);
    for (int i=1; i<tmp; i++) {
        v.pb(lca(v[i], v[i-1]));
    }
    sort(all(v), cmp);
    v.erase(unique(all(v)), v.end());
    int idx = 0;
    stack<ii> st;
    for (auto it: v) {
        while (sz(st) && !is_par(st.top().fi, it)) {
            st.pop();
        }
        idx++;
        if (sz(st)) {
            adj_[st.top().se].pb({idx, d[it]-d[st.top().fi]});
            adj_[idx].pb({st.top().se, d[it]-d[st.top().fi]});
        }
        st.push({it, idx});
    }
    dfs_solve(1, 0);
    return ans;
}

Compilation message (stderr)

factories.cpp:11:41: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const int N = 5e5+5, mod = 1e9+7, inf = 1e18, L = 19;
      |                                         ^~~~

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