oj.uz

Submission #943292

# Submission time Handle Problem Language Result Execution time Memory
943292 2024-03-11T10:11:49 Z ByeWorld Factories (JOI14_factories) C++14
0 / 100
 1810 ms 198000 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];
int 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, wei = ed.se;
		if(nx == par || rem[nx]) continue;
		subtree(nx, nw);
        siz[nw] += siz[nx];
	}
}
int find(int nw){
    subtree(nw);
    int 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, int 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);
    ll ans = INF;
    for(int i=0; i<T; i++) ans = min(ans, que(Y[i]+1));
    for(int i=0; i<S; i++) rst(X[i]+1);
    return ans;
}

Compilation message

factories.cpp: In function 'void subtree(int, int)':
factories.cpp:25:25: warning: unused variable 'wei' [-Wunused-variable]
   25 |         int nx = ed.fi, wei = ed.se;
      |                         ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35416 KB Output is correct
2 Correct 196 ms 51168 KB Output is correct
3 Incorrect 218 ms 51536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35672 KB Output is correct
2 Correct 1232 ms 193796 KB Output is correct
3 Incorrect 1810 ms 198000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35416 KB Output is correct
2 Correct 196 ms 51168 KB Output is correct
3 Incorrect 218 ms 51536 KB Output isn't correct
4 Halted 0 ms 0 KB -