oj.uz

Submission #1025692

# Submission time Handle Problem Language Result Execution time Memory
1025692 2024-07-17T08:48:35 Z khanhtb Factories (JOI14_factories) C++14
100 / 100
 2958 ms 254548 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;
const ll inf = 2e18;
const ll blocksz = 320;
const ll mxn = 1e6+8;
vpll g[mxn],vg[mxn];
ll n,q,tin[mxn],tout[mxn],tdfs,h[mxn],up[mxn][20],d[mxn];
void dfs_pre(ll u, ll p){
    tin[u] = ++tdfs;
    for(pll ed:g[u]){
        ll v = ed.fi, w = ed.se;
        if(v == p) continue;
        h[v] = h[u]+1;
        d[v] = d[u]+w;
        up[v][0] = u;
        for(ll i = 1; i < 20; i++) up[v][i] = up[up[v][i-1]][i-1]; 
        dfs_pre(v,u);
    }
    tout[u] = tdfs;
}
ll lca(ll u, ll v){
    if(h[u] < h[v]) swap(u,v);
    ll k = h[u]-h[v];
    for(ll i = 19; i >= 0; i--){
        if(k>>i&1) u = up[u][i];
    }
    if(u == v) return u;
    for(ll i = 19; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}
ll dist(ll u, ll v){
    return d[u]+d[v]-2*d[lca(u,v)];
}
bool is_anc(ll u, ll v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll dp[mxn][2];
bool mark1[mxn],mark2[mxn];
void dfs(ll u, ll p){
    dp[u][0] = inf, dp[u][1] = inf;
    if(mark1[u]) dp[u][0] = 0;
    if(mark2[u]) dp[u][1] = 0;
    for(pll ed:vg[u]){
        ll v = ed.fi, w = ed.se;
        if(v == p) continue;
        dfs(v,u);
        dp[u][0] = min(dp[u][0],dp[v][0]+w);
        dp[u][1] = min(dp[u][1],dp[v][1]+w);
    }
}
void Init(int N, int A[], int B[], int D[]){
    for(ll i = 0; i < N-1; i++){
        g[A[i]].pb({B[i],D[i]});
        g[B[i]].pb({A[i],D[i]});
    }
    dfs_pre(0,-1);
}
long long Query(int S, int X[], int T, int Y[]){
    vi vertex;
    for(ll i = 0; i < S; i++){
        vertex.pb(X[i]);
        mark1[X[i]] = 1;
    }
    for(ll i = 0; i < T; i++){
        vertex.pb(Y[i]);
        mark2[Y[i]] = 1;    
    }
    sort(all(vertex),[&](ll u, ll v){
        return tin[u] < tin[v];
    });
    ll m = vertex.size();
    for(ll i = 1; i < m; i++){
        ll l = lca(vertex[i-1],vertex[i]);
        vertex.pb(l);
    }
    sort(all(vertex),[&](ll u, ll v){
        return tin[u] < tin[v];
    });
    vertex.erase(unique(all(vertex)),vertex.end());
    stack<ll> st;
    for(ll v:vertex){
        while(st.size() && !is_anc(st.top(),v)) st.pop(); 
        if(st.size()){
            vg[st.top()].pb({v,dist(v,st.top())});
            vg[v].pb({st.top(),dist(v,st.top())});
        }
        st.push(v);
    }
    dfs(vertex.front(),-1);
    ll ans = inf;
    for(ll v:vertex){
        ans = min(ans,dp[v][0]+dp[v][1]);   
    }
    for(ll v:vertex) vg[v].clear(),mark1[v] = mark2[v] = 0;
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 70236 KB Output is correct
2 Correct 720 ms 75092 KB Output is correct
3 Correct 765 ms 74832 KB Output is correct
4 Correct 743 ms 75164 KB Output is correct
5 Correct 577 ms 75348 KB Output is correct
6 Correct 518 ms 74832 KB Output is correct
7 Correct 744 ms 74836 KB Output is correct
8 Correct 733 ms 75168 KB Output is correct
9 Correct 602 ms 75348 KB Output is correct
10 Correct 493 ms 75028 KB Output is correct
11 Correct 715 ms 74836 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 70232 KB Output is correct
2 Correct 1252 ms 212540 KB Output is correct
3 Correct 1563 ms 221252 KB Output is correct
4 Correct 937 ms 213144 KB Output is correct
5 Correct 1612 ms 254548 KB Output is correct
6 Correct 1696 ms 221180 KB Output is correct
7 Correct 1141 ms 102728 KB Output is correct
8 Correct 592 ms 101816 KB Output is correct
9 Correct 841 ms 107640 KB Output is correct
10 Correct 1136 ms 103340 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 70236 KB Output is correct
2 Correct 720 ms 75092 KB Output is correct
3 Correct 765 ms 74832 KB Output is correct
4 Correct 743 ms 75164 KB Output is correct
5 Correct 577 ms 75348 KB Output is correct
6 Correct 518 ms 74832 KB Output is correct
7 Correct 744 ms 74836 KB Output is correct
8 Correct 733 ms 75168 KB Output is correct
9 Correct 602 ms 75348 KB Output is correct
10 Correct 493 ms 75028 KB Output is correct
11 Correct 715 ms 74836 KB Output is correct
12 Correct 12 ms 70232 KB Output is correct
13 Correct 1252 ms 212540 KB Output is correct
14 Correct 1563 ms 221252 KB Output is correct
15 Correct 937 ms 213144 KB Output is correct
16 Correct 1612 ms 254548 KB Output is correct
17 Correct 1696 ms 221180 KB Output is correct
18 Correct 1141 ms 102728 KB Output is correct
19 Correct 592 ms 101816 KB Output is correct
20 Correct 841 ms 107640 KB Output is correct
21 Correct 1136 ms 103340 KB Output is correct
22 Correct 2442 ms 224856 KB Output is correct
23 Correct 2300 ms 222892 KB Output is correct
24 Correct 2958 ms 228252 KB Output is correct
25 Correct 2762 ms 230568 KB Output is correct
26 Correct 2895 ms 221524 KB Output is correct
27 Correct 2677 ms 252796 KB Output is correct
28 Correct 1573 ms 216240 KB Output is correct
29 Correct 2930 ms 221512 KB Output is correct
30 Correct 2824 ms 220492 KB Output is correct
31 Correct 2947 ms 219732 KB Output is correct
32 Correct 1030 ms 110744 KB Output is correct
33 Correct 748 ms 105948 KB Output is correct
34 Correct 1099 ms 102736 KB Output is correct
35 Correct 1045 ms 102540 KB Output is correct
36 Correct 1162 ms 104016 KB Output is correct
37 Correct 1098 ms 103764 KB Output is correct