Submission #1290286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290286		Bahamin	Factories (JOI14_factories)	C++20	100 / 100	2718 ms	175248 KiB

factories

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

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long 
#define all(a) (a).begin(), (a).end()

const int MAX_N = 5e5 + 5;
const int LOG = 30;
const ll INF = 1e18;

vector<pair<int, int>> adj[MAX_N];
int par[MAX_N][LOG];
ll dis[MAX_N];
int st[MAX_N];
int fi[MAX_N];
int h[MAX_N];
int timer = 0;
int n;

void dfs0(int u, int p)
{
    st[u] = timer++;
    par[u][0] = p;
    for (int i = 1; i < LOG; i++) par[u][i] = par[par[u][i - 1]][i - 1];
    for (auto v : adj[u]) if (v.first != p) h[v.first] = h[u] + 1, dis[v.first] = dis[u] + v.second, dfs0(v.first, u);
    fi[u] = timer;
}

int getpar(int u, int k)
{
    for (int i = 0; i < LOG; i++) if (k & (1 << i)) u = par[u][i];
    return u;
}

int lca(int u, int v)
{
    if (h[u] < h[v]) swap(u, v);
    u = getpar(u, h[u] - h[v]);
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; i--) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}

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

vector<int> adj2[MAX_N];
int mark[MAX_N];
ll dp[MAX_N][2];
ll ans = INF;

void dfs(int u)
{
    dp[u][0] = dp[u][1] = INF;
    if (mark[u]) dp[u][mark[u] - 1] = dis[u];
    for (auto v : adj2[u]) dfs(v), dp[u][0] = min(dp[u][0], dp[v][0]), dp[u][1] = min(dp[u][1], dp[v][1]);
    ans = min(ans, dp[u][0] + dp[u][1] - 2 * dis[u]);
}

long long Query(int S, int X[], int T, int Y[]) {
    set<int> al1;
    vector<pair<int, int>> al2;
    for (int i = 0; i < S; i++) X[i]++, al1.insert(X[i]), al2.push_back({st[X[i]], X[i]});
    for (int i = 0; i < T; i++)
    {
        Y[i]++;
        if (al1.find(Y[i]) != al1.end()) return 0;
        al2.push_back({st[Y[i]], Y[i]});
    }
    sort(all(al2));
    int sz = al2.size();
    for (int i = 0; i < sz - 1; i++)
    {
        int lc = lca(al2[i].second, al2[i + 1].second);
        al2.push_back({st[lc], lc});
    }
    sort(all(al2));
    al2.resize(unique(all(al2)) - al2.begin());
    for (auto x : al2) mark[x.second] = 0, adj2[x.second].clear();
    vector<int> al3({al2[0].second});
    for (int i = 1; i < al2.size(); i++)
    {
        while (fi[al3.back()] <= al2[i].first) al3.pop_back();
        adj2[al3.back()].push_back(al2[i].second);
        al3.push_back(al2[i].second);
    }
    for (int i = 0; i < S; i++) mark[X[i]] = 1;
    for (int i = 0; i < T; i++) mark[Y[i]] = 2;
    ans = INF;
    dfs(al2[0].second);
    return ans;
}

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