oj.uz

Submission #1108996

# Submission time Handle Problem Language Result Execution time Memory
1108996 2024-11-05T18:36:49 Z doducanh Factories (JOI14_factories) C++14
0 / 100
 15 ms 46328 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,ll>
const ll maxn=5e5+7;
const ll inf=1e15+7;
vector<vector<pair<int,ll>>>adj(maxn);
vector<int>sz(maxn,0);
vector<bool>used(maxn,0);
vector<ll>minn(maxn,inf);
vector<vector<pair<int,ll>>>ancestors(maxn);
int dfs(int u,int par)
{
    sz[u]=1;
    for(ii pp:adj[u]){
        int v=pp.fi;
        if(v==par||used[v])continue;
        sz[u]+=dfs(v,u);
    }
    return sz[u];
}
void dfs2(int u,int par,int cen,ll depth)
{
    ancestors[u].push_back({cen,depth});
    for(ii pp:adj[u]){
        int v=pp.fi;
        ll w=pp.se;
        if(v==par||used[v])continue;
        dfs2(v,u,cen,depth+w);
    }
}
int getcen(int u,int par,int treesize)
{
    for(ii pp:adj[u]){
        int v=pp.fi;
        if(v==par||used[v])continue;
        if((sz[v]<<1)>treesize)return getcen(v,u,treesize);
    }
    return u;
}
void buildcen(int u,int par)
{
    int C=getcen(u,-1,dfs(u,-1));
    dfs2(C,-1,C,0);
    used[C]=1;
    for(ii pp:adj[u]){
        int v=pp.fi;
        if(used[v])continue;
        buildcen(v,C);
    }
}
void Init(int N,int A[],int B[],int D[])
{
    for(int i=0;i<N-1;i++){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    buildcen(0,-1);
}
long long Query(int S, int X[], int T, int Y[])
{
    for(int i=0;i<T;i++){
        for(pair<int,long long> y:ancestors[Y[i]]){
            minn[y.fi]=inf;
        }
    }
    for(int i=0;i<S;i++){
        for(pair<int,ll> y:ancestors[X[i]]){
            minn[y.fi]=min(minn[y.fi],y.se);
        }
    }
    ll ans=inf;
    for(int i=0;i<T;i++){
        for(pair<int,ll> y:ancestors[Y[i]]){
            ans=min(ans,minn[y.fi]+y.se);
        }
    }
    return ans;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

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