oj.uz

답안 #1025687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025687 2024-07-17T08:45:03 Z khanhtb 공장들 (JOI14_factories) C++14
0 / 100
 25 ms 70232 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 = 0; i < 20; i++){
        if(k>>i&1) u = up[u][i];
    }
    if(u == v) return u;
    for(ll i = 0; i < 20; 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;
}
// signed main(){
//     int A[] = {0, 1, 2, 2, 4, 1};
//     int B[] = {1, 2, 3, 4, 5, 6};
//     int C[] = {4, 4, 5, 6, 5, 3};
//     Init(7, A, B, C);
//     int X[] = {0, 6};
//     int Y[] = {3, 4};
//     cout << Query(2, X, 2, Y) << '\n'; //returns 12.
//     int X1[] = {0, 1, 3};
//     int Y1[] = {4, 6};
//     cout << Query(3, X1, 2, Y1) << '\n'; //returns 3.
//     int X2[] = {2};
//     int Y2[] = {5};
//     cout << Query(1, X2, 1, Y2); //returns 11.
// }

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 70232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 70168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 70232 KB Output isn't correct
2 Halted 0 ms 0 KB -