Submission #480092

#	Time	Username	Problem	Language	Result	Execution time	Memory
480092		duchung	Factories (JOI14_factories)	C++17	100 / 100	5136 ms	194944 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67