oj.uz

Submission #1000281

# Submission time Handle Problem Language Result Execution time Memory
1000281 2024-06-17T08:03:19 Z MarwenElarbi Factories (JOI14_factories) C++17
0 / 100
 9 ms 45540 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=5e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifndef FACTORIES_H_
#define FACTORIES_H_
vector<pair<int,int>> adj[nax];
int sz[nax];
bool removed[nax];
vector<pair<int,ll>> parent[nax];
long long ans[nax];
int get_sz(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        sz[x]+=get_sz(u.fi,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        if(sz[u.fi]*2>t_sz) return get_centroid(u.fi,t_sz,x);
    }
    return x;
}
void get_dist(int x,int centroid,int p,long long cur){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        cur+=u.se;
        get_dist(u.fi,centroid,x,cur);
        cur-=u.se;
    }
    parent[x].pb({centroid,cur});
}
void build(int x){
    int centroid=get_centroid(x,get_sz(x,-1),-1);
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        get_dist(u.fi,centroid,centroid,u.se);
    }
    removed[centroid]=1;
    for(auto u:adj[x]){
        if(removed[u.fi]) continue;
        build(u.fi);
    }
    return;
}
void paint(int x){
    for(auto u:parent[x]){
        ans[u.fi]=min(ans[u.fi],u.se);
    }
    ans[x]=0;
    return;
}
void init_paint(int x){
    for(auto u:parent[x]){
        ans[u.fi]=1e18;
    }
    ans[x]=1e18;
    return;
}
long long get_ans(int x){
    ll res=ans[x];
    for(auto u:parent[x]){
        res=min(res,u.se+ans[u.fi]);
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]) {
    int n=N;
    for (int i = 0; i < n; ++i) ans[i]=1e18;
    for (int i = 0; i < n-1; ++i)
    {
        adj[A[i]].pb({B[i],D[i]});
        adj[B[i]].pb({A[i],D[i]});
    }
    build(0);
    return;
}
long long Query(int S, int X[], int T, int Y[]){
    for (int i = 0; i < T; ++i)
    {
        paint(Y[i]);
    }
    ll res=1e18;
    for (int i = 0; i < S; ++i)
    {
        res=min(res,get_ans(X[i]));
    }
    for (int i = 0; i < T; ++i)
    {
        init_paint(Y[i]);
    }
    return res;
}
#endif  /* FACTORIES_H_ */

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 45540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 45404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 45540 KB Output isn't correct
2 Halted 0 ms 0 KB -