oj.uz

Submission #480092

# Submission time Handle Problem Language Result Execution time Memory
480092 2021-10-14T14:44:07 Z duchung Factories (JOI14_factories) C++17
100 / 100
 5136 ms 194944 KB 
#include "factories.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 5e5 + 5;
const ll INF = 1e18;

int top = 0 , timer = 0;
vector<pair<int , ll>> edge[N];
int tin[N] , depth[N] , color[N];
ll d[N];
int up[N][21];

vector<int> Virtual[N];
int st[N];
ll dp[N][3];

void dfs(int u , int p = -1)
{
    tin[u] = ++timer;
    for (auto adj : edge[u])
    {
        int v = adj.first;
        ll w = adj.second;
        if (v == p) continue;

        up[v][0] = u;
        for (int j = 1 ; j <= 20 ; ++j) up[v][j] = up[up[v][j - 1]][j - 1];

        depth[v] = depth[u] + 1;
        d[v] = d[u] + w;

        dfs(v , u);
    }
}

int lca(int u , int v)
{
    if (depth[u] < depth[v]) swap(u , v);

    for (int j = 20 ; j >= 0 ; --j)
    {
        if (depth[u] - (1 << j) >= depth[v])
        {
            u = up[u][j];
        }
    }

    if (u == v) return u;

    for (int j = 20 ; j >= 0 ; --j)
    {
        if (up[u][j] != up[v][j])
        {
            u = up[u][j];
            v = up[v][j];
        }
    }

    return up[u][0];
}

ll dist(int u , int v)
{
    return d[u] + d[v] - 2 * d[lca(u  , v)];
}

void Init(int n , int a[] , int b[] , int d[])
{
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        ++a[i] , ++b[i];
        edge[a[i]].push_back({b[i] , d[i]});
        edge[b[i]].push_back({a[i] , d[i]});
    }
    dfs(1);
}

bool cmp(int x , int y)
{
    return tin[x] < tin[y];
}

ll dfs2(int u , int p = -1)
{
    ll ans = INF;
    dp[u][1] = dp[u][2] = INF;
    for (int v : Virtual[u])
    {
        if (v == p) continue;
        ans = min(ans , dfs2(v , u));

        ll cur = dist(u , v);
        dp[u][1] = min(dp[u][1] , dp[v][1] + cur);
        dp[u][2] = min(dp[u][2] , dp[v][2] + cur);
    }

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

    Virtual[u].clear();
    color[u] = 0;

    return ans;
}

long long Query(int s , int x[] , int t , int y[])
{
    vector<int> a;
    for (int i = 0 ; i < s ; ++i)
    {
        ++x[i];
        color[x[i]] = 1;
        a.push_back(x[i]);
    }
    for (int i = 0 ; i < t ; ++i)
    {
        ++y[i];
        color[y[i]] = 2;
        a.push_back(y[i]);
    }
    sort(a.begin() , a.end() , cmp);

    st[1] = 1;
    top = 1;

    for (int x : a)
    {
        if (x != 1)
        {
            int tmp = lca(x , st[top]);
            if (tmp != st[top])
            {
                while(tin[tmp] < tin[st[top - 1]])
                {
                    Virtual[st[top]].push_back(st[top - 1]);
                    Virtual[st[top - 1]].push_back(st[top]);
                    --top;
                }
                Virtual[tmp].push_back(st[top]);
                Virtual[st[top]].push_back(tmp);

                if (tin[tmp] > tin[st[top - 1]])
                {
                    st[top] = tmp;
                }
                else
                {
                    --top;
                }
            }
            ++top;
            st[top] = x;
        }
    }

    for (int i = 1 ; i < top ; ++i)
    {
        Virtual[st[i]].push_back(st[i + 1]);
        Virtual[st[i + 1]].push_back(st[i]);
    }

    return dfs2(1);
}
/*
int main()
{
    freopen(".inp","r",stdin);
    freopen(".out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n , q;
    cin >> n >> q;

    int a[n] , b[n] , d[n];
    for (int i = 0 ; i < n - 1 ; ++i) cin >> a[i] >> b[i] >> d[i];
    Init(n , a , b , d);

    // return 0;

    while(q--)
    {
        int s , t;
        cin >> s >> t;

        int x[s] , y[t];
        for (int i = 0 ; i < s ; ++i) cin >> x[i];
        for (int i = 0 ; i < t ; ++i) cin >> y[i];
        cout << Query(s , x , t , y) << "\n";
    }

}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24164 KB Output is correct
2 Correct 803 ms 32968 KB Output is correct
3 Correct 985 ms 33060 KB Output is correct
4 Correct 868 ms 33020 KB Output is correct
5 Correct 727 ms 42732 KB Output is correct
6 Correct 708 ms 42484 KB Output is correct
7 Correct 991 ms 42384 KB Output is correct
8 Correct 876 ms 42460 KB Output is correct
9 Correct 736 ms 42800 KB Output is correct
10 Correct 728 ms 42504 KB Output is correct
11 Correct 960 ms 42500 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24012 KB Output is correct
2 Correct 2105 ms 138908 KB Output is correct
3 Correct 3249 ms 141400 KB Output is correct
4 Correct 1549 ms 154776 KB Output is correct
5 Correct 2889 ms 190480 KB Output is correct
6 Correct 3497 ms 161632 KB Output is correct
7 Correct 2656 ms 69624 KB Output is correct
8 Correct 1375 ms 69724 KB Output is correct
9 Correct 2180 ms 74256 KB Output is correct
10 Correct 2661 ms 71084 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24164 KB Output is correct
2 Correct 803 ms 32968 KB Output is correct
3 Correct 985 ms 33060 KB Output is correct
4 Correct 868 ms 33020 KB Output is correct
5 Correct 727 ms 42732 KB Output is correct
6 Correct 708 ms 42484 KB Output is correct
7 Correct 991 ms 42384 KB Output is correct
8 Correct 876 ms 42460 KB Output is correct
9 Correct 736 ms 42800 KB Output is correct
10 Correct 728 ms 42504 KB Output is correct
11 Correct 960 ms 42500 KB Output is correct
12 Correct 17 ms 24012 KB Output is correct
13 Correct 2105 ms 138908 KB Output is correct
14 Correct 3249 ms 141400 KB Output is correct
15 Correct 1549 ms 154776 KB Output is correct
16 Correct 2889 ms 190480 KB Output is correct
17 Correct 3497 ms 161632 KB Output is correct
18 Correct 2656 ms 69624 KB Output is correct
19 Correct 1375 ms 69724 KB Output is correct
20 Correct 2180 ms 74256 KB Output is correct
21 Correct 2661 ms 71084 KB Output is correct
22 Correct 3609 ms 166900 KB Output is correct
23 Correct 3384 ms 169168 KB Output is correct
24 Correct 4041 ms 169824 KB Output is correct
25 Correct 4274 ms 173088 KB Output is correct
26 Correct 5007 ms 169132 KB Output is correct
27 Correct 3636 ms 194944 KB Output is correct
28 Correct 2490 ms 167064 KB Output is correct
29 Correct 5136 ms 168732 KB Output is correct
30 Correct 5111 ms 168092 KB Output is correct
31 Correct 5018 ms 168836 KB Output is correct
32 Correct 1832 ms 76188 KB Output is correct
33 Correct 1493 ms 71380 KB Output is correct
34 Correct 2049 ms 67408 KB Output is correct
35 Correct 2101 ms 67304 KB Output is correct
36 Correct 2579 ms 68080 KB Output is correct
37 Correct 2561 ms 67928 KB Output is correct