Submission #152322

#	Time	Username	Problem	Language	Result	Execution time	Memory
152322		karma	Factories (JOI14_factories)	C++14	100 / 100	4806 ms	174432 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define pb      emplace_back
#define mp      make_pair
#define fi      first
#define se      second
#define ll      long long

using namespace std;

const int N = int(5e5) + 7;
const int logN = 21;
const ll oo = (ll)1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

static int in[N], out[N], h[N], p[N][logN], Ti, c[N];
ll d[N], res;
pll f[N];
vector<pii> a[N], v;
vector<int> g[N], st;

void DFS(int u) {
     in[u] = ++Ti;
     for(int i = 1; i < logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
     for(pii adj: a[u]) {
        if(in[adj.fi]) continue;
        d[adj.fi] = d[u] + adj.se;
        p[adj.fi][0] = u, h[adj.fi] = h[u] + 1;
        DFS(adj.fi);
     }
     out[u] = Ti;
}

int LCA(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    for(int i = logN - 1; i >= 0; --i)
        if(h[u] - (1 << i) >= h[v]) u = p[u][i];
    if(u == v) return u;
    for(int i = logN - 1; i >= 0; --i)
        if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
    return p[u][0];
}

void Init(int n, int A[], int B[], int D[]) {
     for(int i = 0; i + 1 < n; ++i) a[A[i]].pb(B[i], D[i]), a[B[i]].pb(A[i], D[i]);
     DFS(0);
}
//fi - u, se - v
void GetAns(int u) {
     if(c[u] == 1) f[u] = mp(d[u], oo);
     else if(c[u] == 2) f[u] = mp(oo, d[u]);
     else f[u] = mp(oo, oo);
     for(int v: g[u]) {
        GetAns(v);
        res = min({res, f[v].fi + f[u].se - 2 * d[u], f[v].se + f[u].fi - 2 * d[u]});
        f[u].fi = min(f[u].fi, f[v].fi);
        f[u].se = min(f[u].se, f[v].se);
     }
}

ll Query(int S, int X[], int T, int Y[])
{
   v.clear(); st.clear();
   for(int i = 0; i < S; ++i) c[X[i]] = 1, v.pb(in[X[i]], X[i]);
   for(int i = 0; i < T; ++i) c[Y[i]] = 2, v.pb(in[Y[i]], Y[i]);
   sort(v.begin(), v.end());
   for(int i = 0; i < S + T - 1; ++i) {
      int lca = LCA(v[i].se, v[i + 1].se);
      v.pb(in[lca], lca);
   }
   v.pb(in[0], 0);
   sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
   for(pii p: v) {
      g[p.se].clear();
      while(!st.empty() && out[st.back()] < p.fi) st.pop_back();
      if(st.size()) g[st.back()].pb(p.se);
      st.pb(p.se);
   }
   res = oo; GetAns(0);
   for(int i = 0; i < S; ++i) c[X[i]] = 0;
   for(int i = 0; i < T; ++i) c[Y[i]] = 0;
   return res;
}
//
//int _n, q, A[N], B[N], D[N], S, T, X[N], Y[N];
//
//int main() {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
//    if(fopen("test.inp", "r")) {
//        freopen("test.inp", "r", stdin);
//        freopen("test.out", "w", stdout);
//    }
//    cin >> _n >> q;
//    for(int i = 0; i + 1 < _n; ++i) cin >> A[i] >> B[i] >> D[i];
//    Init(_n, A, B, D);
//    for(int i = 0; i < q; ++i) {
//        cin >> S >> T;
//        for(int j = 0; j < S; ++j) cin >> X[j];
//        for(int j = 0; j < T; ++j) cin >> Y[j];
//        cout << Query(S, X, T, Y) << '\n';
//    }
//}

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