Submission #964968

#	Time	Username	Problem	Language	Result	Execution time	Memory
964968		teo_thrash	Factories (JOI14_factories)	C++14	0 / 100	26 ms	51748 KiB

factories

// it is your desire to work hard

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn=5e5+3;
const int mod=1e9+7;

int n;
vector<pii> nbrs[maxn];
bool done[maxn+1];
int sz[maxn];
vector<pii> dist[maxn];
int level[maxn];
int par[maxn];

int least_first[maxn], least_sec[maxn];

void calc_sizes(int x, int y){
    sz[x]=1;
    for(auto u: nbrs[x]){
        if(!done[u.first] and u.first!=y){
            calc_sizes(u.first, x);

            sz[x]+=sz[u.first];
        }
    }

    return ;
}

void calc_dist(int x, int y, int d=0, int p=-1){
    dist[x].pb({y, d});
    for(auto u: nbrs[x]){
        if(!done[u.first] and u.first!=p){
            calc_dist(u.first, y, d+u.second, x);
        }
    }
}

int find_centroid(int x, int curr_sz, int y=-1){

    for(auto u: nbrs[x]){
        if(u.first==y or done[u.first]) continue;
        if(sz[u.first]>curr_sz/2) return find_centroid(u.first, curr_sz, x);
    }

    return x;
}

void centroid_decomp(int x, int lvl=0, int prev=-1){
    calc_sizes(x, -1);
    int centroid = find_centroid(x, sz[x], -1);
    calc_dist(centroid, centroid);
    done[centroid] = true;
    level[centroid] = lvl;

    par[centroid] = prev;

    for(auto u: nbrs[centroid]){
        if(done[u.first]) continue;
        centroid_decomp(u.first, lvl+1, x);
    }

    return ;
}

void Init(int N, int A[], int B[], int D[]){
    n=N;

    for(int i=0; i<n; i++){
        nbrs[A[i]].pb({B[i], D[i]});
    }

    return ;
}

int first[maxn], sec[maxn];

long long Query(int S, int X[], int T, int Y[]){
    int s=S, t=T;

    for(int i=0; i<s; i++){
        first[i] = X[i];
    }
    for(int i=0; i<t; i++){
        sec[i] = Y[i];
    }

    bool found_1=true, found_2=true;
    int steps[2][maxn];

    for(int i=0; i<s; i++){
        steps[0][i] = dist[first[i]].size()-1;
    }
    for(int i=0; i<t; i++){
        steps[1][i] = dist[sec[i]].size()-1;
    }

    for(int i=0; i<=n; i++){
        least_first[i] = INT_MAX;
        least_sec[i] = INT_MAX;
    }

    while(!found_1 and !found_2){
        for(int i=0; i<s; i++){
            if(par[first[i]]!=-1){
                least_first[par[first[i]]] = min(least_first[par[first[i]]], dist[X[i]][steps[0][i]].second);
                first[i] = par[first[i]];

                if(steps[0][i]>0) steps[0][i]--;
            }
        }

        for(int i=0; i<t; i++){
            if(par[sec[i]]!=-1){
                least_sec[par[sec[i]]] = min(least_sec[par[sec[i]]], dist[X[i]][steps[0][i]].second);
                sec[i] = par[sec[i]];

                if(steps[1][i]>0) steps[0][i]--;
            }
        }

    }
    int ans=INT_MAX;
    for(int i=0; i<=n; i++){
        ans=min(ans, least_first[i]+least_sec[i]);
    }
    return ans;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67