제출 #246908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246908		receed	공장들 (JOI14_factories)	C++14	100 / 100	5297 ms	139644 KiB

factories

#include "factories.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 500001, L = 19;
vector<pair<ll, ll>> g[N];
int tin[N], tout[N], ct, up[L][N], th[N], par[N], st[N], li[N * 2];
ll h[N], d1[N], d2[N], inf = 1e16;

void dfs(int v, int p) {
    up[0][v] = p;
    tin[v] = ++ct;
    for (auto &u : g[v])
        if (u.first != p) {
            h[u.first] = h[v] + u.second;
            th[u.first] = th[v] + 1;
            dfs(u.first, v);
        }
    tout[v] = ++ct;
}

int isp(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

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

void Init(int n, int a[], int b[], int d[]) {
    rep(i, n - 1) {
        g[a[i]].push_back({b[i], d[i]});
        g[b[i]].push_back({a[i], d[i]});
    }
    dfs(0, 0);
    rep(i, L - 1)
        rep(j, n)
            up[i + 1][j] = up[i][up[i][j]];
    rep(i, n)
        d1[i] = d2[i] = inf;
}

long long Query(int s, int x[], int t, int y[]) {
    int lp = 0;
    rep(i, s) {
        li[lp++] = x[i];
        d1[x[i]] = 0;
    }
    rep(i, t) {
        li[lp++] = y[i];
        d2[y[i]] = 0;
    }
    sort(li, li + lp, [](int v1, int v2) {return tin[v1] < tin[v2];});
    int k = lp;
    rep(i, k - 1)
        li[lp++] = lca(li[i], li[i + 1]);
    sort(li, li + lp, [](int v1, int v2) {return tin[v1] < tin[v2];});
    lp = unique(li, li + lp) - li;
    int sp = 0;
    rep(j, lp) {
        int i = li[j];
        if (sp == 0)
            st[sp++] = i;
        else {
            while (tout[st[sp - 1]] < tout[i])
                sp--;
            par[i] = st[sp - 1];
            st[sp++] = i;
        }
    }
    ll ans = inf;
    for (int i = lp - 1; i > 0; i--) {
        ll v = li[i], cd = h[v] - h[par[v]];
        d1[v] += cd;
        d2[v] += cd;
        ans = min(ans, min(d1[v] + d2[par[v]], d2[v] + d1[par[v]]));
        d1[par[v]] = min(d1[par[v]], d1[v]);
        d2[par[v]] = min(d2[par[v]], d2[v]);
    }
    rep(i, lp)
        d1[li[i]] = d2[li[i]] = inf;
    return ans;
}

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