oj.uz

답안 #1025695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025695 2024-07-17T08:49:43 Z vjudge1 공장들 (JOI14_factories) C++17
100 / 100
 2895 ms 252948 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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 70236 KB Output is correct
2 Correct 711 ms 75048 KB Output is correct
3 Correct 735 ms 75032 KB Output is correct
4 Correct 710 ms 75160 KB Output is correct
5 Correct 600 ms 75304 KB Output is correct
6 Correct 477 ms 74836 KB Output is correct
7 Correct 737 ms 75028 KB Output is correct
8 Correct 724 ms 75184 KB Output is correct
9 Correct 608 ms 75292 KB Output is correct
10 Correct 506 ms 75032 KB Output is correct
11 Correct 763 ms 75044 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 70236 KB Output is correct
2 Correct 1337 ms 212508 KB Output is correct
3 Correct 1586 ms 221268 KB Output is correct
4 Correct 896 ms 213048 KB Output is correct
5 Correct 1614 ms 251756 KB Output is correct
6 Correct 1741 ms 221228 KB Output is correct
7 Correct 1133 ms 102992 KB Output is correct
8 Correct 570 ms 101820 KB Output is correct
9 Correct 857 ms 107664 KB Output is correct
10 Correct 1115 ms 103152 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 70236 KB Output is correct
2 Correct 711 ms 75048 KB Output is correct
3 Correct 735 ms 75032 KB Output is correct
4 Correct 710 ms 75160 KB Output is correct
5 Correct 600 ms 75304 KB Output is correct
6 Correct 477 ms 74836 KB Output is correct
7 Correct 737 ms 75028 KB Output is correct
8 Correct 724 ms 75184 KB Output is correct
9 Correct 608 ms 75292 KB Output is correct
10 Correct 506 ms 75032 KB Output is correct
11 Correct 763 ms 75044 KB Output is correct
12 Correct 14 ms 70236 KB Output is correct
13 Correct 1337 ms 212508 KB Output is correct
14 Correct 1586 ms 221268 KB Output is correct
15 Correct 896 ms 213048 KB Output is correct
16 Correct 1614 ms 251756 KB Output is correct
17 Correct 1741 ms 221228 KB Output is correct
18 Correct 1133 ms 102992 KB Output is correct
19 Correct 570 ms 101820 KB Output is correct
20 Correct 857 ms 107664 KB Output is correct
21 Correct 1115 ms 103152 KB Output is correct
22 Correct 2476 ms 224840 KB Output is correct
23 Correct 2242 ms 222952 KB Output is correct
24 Correct 2848 ms 228236 KB Output is correct
25 Correct 2669 ms 230432 KB Output is correct
26 Correct 2775 ms 221600 KB Output is correct
27 Correct 2760 ms 252948 KB Output is correct
28 Correct 1688 ms 216136 KB Output is correct
29 Correct 2895 ms 221384 KB Output is correct
30 Correct 2721 ms 220340 KB Output is correct
31 Correct 2644 ms 219616 KB Output is correct
32 Correct 1039 ms 110704 KB Output is correct
33 Correct 714 ms 105408 KB Output is correct
34 Correct 1022 ms 102520 KB Output is correct
35 Correct 952 ms 102548 KB Output is correct
36 Correct 1102 ms 104020 KB Output is correct
37 Correct 1138 ms 103760 KB Output is correct