Submission #1291026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291026		Sofiatpc	Factories (JOI14_factories)	C++20	0 / 100	8092 ms	99856 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
#define sz(v) (int)v.size()
typedef long long ll;
const int MAXN = 5*1e5+5;
const ll INF = 1e16;
vector<int> adj[MAXN];
vector<ll> w[MAXN];
vector< pair<int,ll> > anc[MAXN];
int sub[MAXN], marc[MAXN], cen, tot;
ll ans[MAXN];

void dfsSub(int s, int p){
    sub[s] = 1;
    for(int viz : adj[s])
        if(viz != p){
            dfsSub(viz,s);
            sub[s] += sub[viz];
        }
}

int achaCentroid(int s, int p, int tam){
    for(int viz : adj[s])
        if(viz != p && !marc[viz] && sub[viz] > tam)return achaCentroid(viz,s,tam);
    return s;
}

void dfs(int s, int p, int dist){
    anc[s].emplace_back(cen, dist);
    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i];
        if(viz != p && !marc[viz])dfs(viz,s,dist+w[s][i]);
    }
}

void tree(int s, int tam){
    cen = achaCentroid(s,-1,tam/2);
    dfs(cen,-1,0);

    dfsSub(cen,-1); marc[cen] = 1;
    for(int viz : adj[cen])
        if(!marc[viz])tree(viz,sub[viz]);
}

void Init(int n, int a[], int b[], int d[]) {
    tot = n;
    for(int i = 0; i < n-1; i++){
        adj[a[i]].push_back(b[i]); w[a[i]].push_back(d[i]);
        adj[b[i]].push_back(a[i]); w[b[i]].push_back(d[i]);
    }

    dfsSub(0,-1);
    tree(0,n);
}

void updateCD(int i){
    for(int j = 0; j < sz(anc[i]); j++)
        ans[anc[i][j].fi] = min(ans[anc[i][j].fi], anc[i][j].sc);
}

ll queryCD(int i){
    ll resp = INF;
    for(int j = 0; j < sz(anc[i]); j++)
        resp = min(resp, ans[anc[i][j].fi] + anc[i][j].sc);
    return resp;
}

long long Query(int s, int x[], int t, int y[]) {
    for(int i = 0; i < tot; i++)ans[i] = INF;

    for(int i = 0; i < s; i++)updateCD(x[i]);

    ll resp = INF;
    for(int i = 0; i < t; i++)resp = min(resp, queryCD(y[i]));

  return resp;
}

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