oj.uz

Submission #152322

# Submission time Handle Problem Language Result Execution time Memory
152322 2019-09-07T14:37:31 Z karma Factories (JOI14_factories) C++14
100 / 100
 4806 ms 174432 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 24264 KB Output is correct
2 Correct 1083 ms 42456 KB Output is correct
3 Correct 1074 ms 42448 KB Output is correct
4 Correct 1115 ms 42464 KB Output is correct
5 Correct 1095 ms 42696 KB Output is correct
6 Correct 779 ms 42284 KB Output is correct
7 Correct 1071 ms 42372 KB Output is correct
8 Correct 1065 ms 42580 KB Output is correct
9 Correct 993 ms 42556 KB Output is correct
10 Correct 749 ms 42304 KB Output is correct
11 Correct 1087 ms 42508 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24056 KB Output is correct
2 Correct 1896 ms 134680 KB Output is correct
3 Correct 2707 ms 135724 KB Output is correct
4 Correct 1433 ms 135120 KB Output is correct
5 Correct 2894 ms 164612 KB Output is correct
6 Correct 2914 ms 138168 KB Output is correct
7 Correct 2169 ms 65008 KB Output is correct
8 Correct 1231 ms 65276 KB Output is correct
9 Correct 2527 ms 70560 KB Output is correct
10 Correct 2103 ms 66364 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 24264 KB Output is correct
2 Correct 1083 ms 42456 KB Output is correct
3 Correct 1074 ms 42448 KB Output is correct
4 Correct 1115 ms 42464 KB Output is correct
5 Correct 1095 ms 42696 KB Output is correct
6 Correct 779 ms 42284 KB Output is correct
7 Correct 1071 ms 42372 KB Output is correct
8 Correct 1065 ms 42580 KB Output is correct
9 Correct 993 ms 42556 KB Output is correct
10 Correct 749 ms 42304 KB Output is correct
11 Correct 1087 ms 42508 KB Output is correct
12 Correct 32 ms 24056 KB Output is correct
13 Correct 1896 ms 134680 KB Output is correct
14 Correct 2707 ms 135724 KB Output is correct
15 Correct 1433 ms 135120 KB Output is correct
16 Correct 2894 ms 164612 KB Output is correct
17 Correct 2914 ms 138168 KB Output is correct
18 Correct 2169 ms 65008 KB Output is correct
19 Correct 1231 ms 65276 KB Output is correct
20 Correct 2527 ms 70560 KB Output is correct
21 Correct 2103 ms 66364 KB Output is correct
22 Correct 3538 ms 148204 KB Output is correct
23 Correct 3134 ms 150208 KB Output is correct
24 Correct 3876 ms 152356 KB Output is correct
25 Correct 3868 ms 155660 KB Output is correct
26 Correct 4537 ms 146340 KB Output is correct
27 Correct 4067 ms 174432 KB Output is correct
28 Correct 2074 ms 149044 KB Output is correct
29 Correct 4806 ms 145264 KB Output is correct
30 Correct 4544 ms 144784 KB Output is correct
31 Correct 4612 ms 145176 KB Output is correct
32 Correct 2112 ms 73012 KB Output is correct
33 Correct 1318 ms 68108 KB Output is correct
34 Correct 1963 ms 63736 KB Output is correct
35 Correct 2001 ms 63524 KB Output is correct
36 Correct 2125 ms 64184 KB Output is correct
37 Correct 2240 ms 64136 KB Output is correct