oj.uz

Submission #943308

# Submission time Handle Problem Language Result Execution time Memory
943308 2024-03-11T10:29:36 Z ByeWorld Factories (JOI14_factories) C++14
100 / 100
 2783 ms 232212 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
const ll INF = 1e18+10;
const int MAXN = 5e5+10;
const int LOG = 21;
 
int n;
vector <pii> adj[MAXN];
ll siz[MAXN], anc[MAXN];
bool rem[MAXN];
 
void subtree(int nw, int par=0){
    siz[nw] = 1;
	for(auto ed : adj[nw]){
        int nx = ed.fi;
		if(nx == par || rem[nx]) continue;
		subtree(nx, nw);
        siz[nw] += siz[nx];
	}
}
ll find(ll nw){
    subtree(nw);
    ll root = nw;
    bool found = 0;
    // if(nw==3){
    //     for(int i=1; i<=n; i++) cout << i << ' ' << siz[i] << " xx\n";
    // }
    //cout<<"in ";
    while(!found){
        found = 1;
        for(auto ed : adj[nw]){ // bisa ke par
            if(rem[ed.fi] || siz[ed.fi] > siz[nw]) continue;
            // ke nx
            if(siz[ed.fi] > siz[root]/2){
                found = 0;
                nw = ed.fi;
                break;
            }
        }
    }
    //cout << root << ' ' << nw << " out\n";
    return nw;
}
 
ll dis[MAXN][LOG+5], dep_cen[MAXN];
void dfs(int nw, int par, ll wei, int dep){
    dis[nw][dep] = wei;
    // cout << nw << " " << wei << endl;
    for(auto nx : adj[nw]){
        if(nx.fi == par || rem[nx.fi]) continue;
        dfs(nx.fi, nw, wei+nx.se, dep);
    }
}
void bd(int nw, int par_cen){
    int cen = find(nw);
    anc[cen] = par_cen;
    dep_cen[cen] = dep_cen[par_cen]+1;
    // cout << cen << ":\n";
    dfs(cen, -1, 0, dep_cen[cen]);
    rem[cen] = 1;
    
    for(auto nx : adj[cen]){
        if(rem[nx.fi]) continue;
        bd(nx.fi, cen);
    }
}
 
ll val[MAXN];
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i=0; i<n-1; i++){
		A[i]++; B[i]++;
        //cout << i << ' ' << A[i] << ' ' << B[i] << " ed\n";
		adj[A[i]].pb(pii(B[i], D[i])); adj[B[i]].pb(pii(A[i], D[i]));
	}
	bd(1, 0);
    //for(int i=1; i<=n; i++) cout << anc[i] << " p\n";
    for(int i=1; i<=n; i++) val[i] = INF;
}
 
void rst(int nw){
    int ANC = nw;
    while(ANC != 0){
        val[ANC] = INF;
        ANC = anc[ANC];
    }
}
void upd(int nw){
    val[nw] = 0;
    int ANC = nw, dep = dep_cen[nw];
    while(ANC != 0){
        ll dist = dis[nw][dep];
        val[ANC] = min(val[ANC], dist);
        ANC = anc[ANC]; dep--;
    }
}
ll que(int nw){
    ll ret = INF;
    int ANC = nw, dep = dep_cen[nw];
    while(ANC != 0){
        ll dist = dis[nw][dep] + val[ANC];
        ret = min(ret, dist);
        ANC = anc[ANC]; dep--;
    }
    return ret;
}
long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<S; i++) upd(X[i]+1);
    //for (int i=1;i<=n;i++) cout<<(val[i]==INF?-1:val[i])<<" ";
    //cout<<endl;
    ll ans = INF;
    for(int i=0; i<T; i++) {
        ans = min(ans, que(Y[i]+1));
        //cout<<que(Y[i]+1)<<' ';
    }
    //cout<<endl;
    for(int i=0; i<S; i++) rst(X[i]+1);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33112 KB Output is correct
2 Correct 242 ms 39764 KB Output is correct
3 Correct 217 ms 39864 KB Output is correct
4 Correct 215 ms 49124 KB Output is correct
5 Correct 228 ms 49492 KB Output is correct
6 Correct 155 ms 49124 KB Output is correct
7 Correct 216 ms 49372 KB Output is correct
8 Correct 221 ms 49236 KB Output is correct
9 Correct 227 ms 49648 KB Output is correct
10 Correct 146 ms 49236 KB Output is correct
11 Correct 218 ms 49348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33116 KB Output is correct
2 Correct 1135 ms 179064 KB Output is correct
3 Correct 1787 ms 183900 KB Output is correct
4 Correct 431 ms 194944 KB Output is correct
5 Correct 2430 ms 232212 KB Output is correct
6 Correct 1961 ms 202716 KB Output is correct
7 Correct 554 ms 84440 KB Output is correct
8 Correct 257 ms 83264 KB Output is correct
9 Correct 611 ms 88144 KB Output is correct
10 Correct 618 ms 85332 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33112 KB Output is correct
2 Correct 242 ms 39764 KB Output is correct
3 Correct 217 ms 39864 KB Output is correct
4 Correct 215 ms 49124 KB Output is correct
5 Correct 228 ms 49492 KB Output is correct
6 Correct 155 ms 49124 KB Output is correct
7 Correct 216 ms 49372 KB Output is correct
8 Correct 221 ms 49236 KB Output is correct
9 Correct 227 ms 49648 KB Output is correct
10 Correct 146 ms 49236 KB Output is correct
11 Correct 218 ms 49348 KB Output is correct
12 Correct 6 ms 33116 KB Output is correct
13 Correct 1135 ms 179064 KB Output is correct
14 Correct 1787 ms 183900 KB Output is correct
15 Correct 431 ms 194944 KB Output is correct
16 Correct 2430 ms 232212 KB Output is correct
17 Correct 1961 ms 202716 KB Output is correct
18 Correct 554 ms 84440 KB Output is correct
19 Correct 257 ms 83264 KB Output is correct
20 Correct 611 ms 88144 KB Output is correct
21 Correct 618 ms 85332 KB Output is correct
22 Correct 1446 ms 202384 KB Output is correct
23 Correct 1387 ms 203956 KB Output is correct
24 Correct 2249 ms 206568 KB Output is correct
25 Correct 2348 ms 208964 KB Output is correct
26 Correct 2328 ms 207136 KB Output is correct
27 Correct 2783 ms 230856 KB Output is correct
28 Correct 554 ms 201392 KB Output is correct
29 Correct 2255 ms 206752 KB Output is correct
30 Correct 2266 ms 206312 KB Output is correct
31 Correct 2236 ms 206740 KB Output is correct
32 Correct 672 ms 88940 KB Output is correct
33 Correct 231 ms 83340 KB Output is correct
34 Correct 398 ms 82516 KB Output is correct
35 Correct 389 ms 82528 KB Output is correct
36 Correct 560 ms 83476 KB Output is correct
37 Correct 556 ms 83536 KB Output is correct