oj.uz

Submission #118633

# Submission time Handle Problem Language Result Execution time Memory
118633 2019-06-19T10:05:14 Z evpipis Factories (JOI14_factories) C++17
100 / 100
 7918 ms 283272 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;

const int len = 5e5+5, lg = 19;
const ll inf = 1e17;
int dep[len], ord[len], tp[len], cnt;
pair<int, ll> par[len], up[lg][len];
ll dp[len][2];
vector<int> vec, st;
vector<ii> adj[len];
vector<pair<int, ll> > nex[len];

void fix(int u){
    ord[u] = cnt++;
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        if (v.fi == par[u].fi)
            continue;

        par[v.fi] = mp(u, v.se);
        dep[v.fi] = dep[u]+1;
        fix(v.fi);
    }
}

int lca(int a, int b){
    if (a == 0 || b == 0)
        return 0;

    if (dep[a] < dep[b])
        swap(a, b);
    for (int j = lg-1; j >= 0; j--)
        if ((1<<j)&(dep[a]-dep[b]))
            a = up[j][a].fi;

    if (a == b)
        return a;

    for (int j = lg-1; j >= 0; j--)
        if (up[j][a].fi != up[j][b].fi)
            a = up[j][a].fi, b = up[j][b].fi;
    return par[a].fi;
}

void Init(int n, int A[], int B[], int D[]){
    for (int i = 0; i < n-1; i++){
        int a = A[i]+1, b = B[i]+1, c = D[i];
        adj[a].pb(mp(b, c));
        adj[b].pb(mp(a, c));
    }

    cnt = dep[1] = 1;
    fix(1);

    for (int i = 1; i <= n; i++)
        up[0][i] = par[i];
    for (int j = 1; (1<<j) < n; j++)
        for (int i = 1; i <= n; i++)
            if (up[j-1][i].fi != 0){
                up[j][i] = up[j-1][up[j-1][i].fi];
                up[j][i].se += up[j-1][i].se;
            }

    for (int i = 0; i <= n; i++)
        tp[i] = 2;
}

bool comp(int a, int b){
    return (ord[a] < ord[b]);
}

ll path(int a, int b){
    ll ans = 0;
    for (int j = lg-1; j >= 0; j--)
        if ((1<<j)&(dep[a]-dep[b]))
            ans += up[j][a].se, a = up[j][a].fi;

    return ans;
}

ll dfs(int u){
    //printf("inside dfs: u = %d\n", u);
    ll ans = inf;

    dp[u][0] = dp[u][1] = inf;
    if (tp[u] == 0)
        dp[u][0] = 0;
    if (tp[u] == 1)
        dp[u][1] = 0;
    for (int j = 0; j < nex[u].size(); j++){
        pair<int, ll> v = nex[u][j];

        ans = min(ans, dfs(v.fi));

        dp[u][0] = min(dp[u][0], dp[v.fi][0]+v.se);
        dp[u][1] = min(dp[u][1], dp[v.fi][1]+v.se);
    }

    ans = min(ans, dp[u][0]+dp[u][1]);

    //clear everything
    tp[u] = 2;
    nex[u].clear();

    return ans;
}

ll Query(int s, int X[], int t, int Y[]){
    for (int i = 0; i < s; i++)
        vec.pb(X[i]+1), tp[vec.back()] = 0;
    for (int i = 0; i < t; i++)
        vec.pb(Y[i]+1), tp[vec.back()] = 1;

    sort(vec.begin(), vec.end(), comp);

    st.pb(0);
    for (int i = 0; i < vec.size(); i++){
        int u = vec[i], p = lca(u, st.back());

        //printf("virtual tree... u = %d, back = %d, lca = %d\n", u, st.back(), p);

        while (st.size() >= 2 && dep[p] <= dep[st[st.size()-2]]){
            int v = st.back();
            st.pop_back();
            nex[st.back()].pb(mp(v, path(v, st.back())));
        }

        if (p != st.back()){
            nex[p].pb(mp(st.back(), path(st.back(), p)));
            st.pop_back();
            st.pb(p);
        }
        st.pb(u);
    }

    for (int i = 0; i+1 < st.size(); i++)
        nex[st[i]].pb(mp(st[i+1], path(st[i+1], st[i])));

    ll ans = dfs(0);
    st.clear();
    vec.clear();

    return ans;
}

Compilation message

factories.cpp: In function 'void fix(int)':
factories.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'll dfs(int)':
factories.cpp:98:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < nex[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:125:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
factories.cpp:144:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i+1 < st.size(); i++)
                     ~~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 24576 KB Output is correct
2 Correct 783 ms 42528 KB Output is correct
3 Correct 946 ms 43000 KB Output is correct
4 Correct 835 ms 43004 KB Output is correct
5 Correct 672 ms 43512 KB Output is correct
6 Correct 595 ms 42360 KB Output is correct
7 Correct 924 ms 43000 KB Output is correct
8 Correct 837 ms 43128 KB Output is correct
9 Correct 710 ms 43384 KB Output is correct
10 Correct 605 ms 42324 KB Output is correct
11 Correct 928 ms 42844 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24184 KB Output is correct
2 Correct 2711 ms 150580 KB Output is correct
3 Correct 4733 ms 230728 KB Output is correct
4 Correct 1701 ms 119852 KB Output is correct
5 Correct 3386 ms 274432 KB Output is correct
6 Correct 5004 ms 232664 KB Output is correct
7 Correct 4399 ms 81068 KB Output is correct
8 Correct 1412 ms 62632 KB Output is correct
9 Correct 3142 ms 89556 KB Output is correct
10 Correct 4520 ms 82368 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 24576 KB Output is correct
2 Correct 783 ms 42528 KB Output is correct
3 Correct 946 ms 43000 KB Output is correct
4 Correct 835 ms 43004 KB Output is correct
5 Correct 672 ms 43512 KB Output is correct
6 Correct 595 ms 42360 KB Output is correct
7 Correct 924 ms 43000 KB Output is correct
8 Correct 837 ms 43128 KB Output is correct
9 Correct 710 ms 43384 KB Output is correct
10 Correct 605 ms 42324 KB Output is correct
11 Correct 928 ms 42844 KB Output is correct
12 Correct 26 ms 24184 KB Output is correct
13 Correct 2711 ms 150580 KB Output is correct
14 Correct 4733 ms 230728 KB Output is correct
15 Correct 1701 ms 119852 KB Output is correct
16 Correct 3386 ms 274432 KB Output is correct
17 Correct 5004 ms 232664 KB Output is correct
18 Correct 4399 ms 81068 KB Output is correct
19 Correct 1412 ms 62632 KB Output is correct
20 Correct 3142 ms 89556 KB Output is correct
21 Correct 4520 ms 82368 KB Output is correct
22 Correct 4102 ms 166512 KB Output is correct
23 Correct 4129 ms 167660 KB Output is correct
24 Correct 5161 ms 248084 KB Output is correct
25 Correct 5566 ms 251260 KB Output is correct
26 Correct 6571 ms 241584 KB Output is correct
27 Correct 4112 ms 283272 KB Output is correct
28 Correct 2643 ms 133700 KB Output is correct
29 Correct 7117 ms 240324 KB Output is correct
30 Correct 7348 ms 239872 KB Output is correct
31 Correct 7918 ms 240176 KB Output is correct
32 Correct 2265 ms 92060 KB Output is correct
33 Correct 1443 ms 65324 KB Output is correct
34 Correct 2443 ms 67192 KB Output is correct
35 Correct 2839 ms 65720 KB Output is correct
36 Correct 3234 ms 80576 KB Output is correct
37 Correct 3236 ms 80436 KB Output is correct