Submission #1291028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291028		Sofiatpc	공장들 (JOI14_factories)	C++20	15 / 100	8087 ms	103756 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 = 1e18;
vector<int> adj[MAXN];
vector<ll> w[MAXN];
vector< pair<int,ll> > anc[MAXN];
int sub[MAXN], marc[MAXN], cen;
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, ll 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[]) {
    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]);
    }

    for(int i = 0; i < n; i++)ans[i] = INF;

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

long long Query(int s, int x[], int t, int y[]) {
    for(int i = 0; i < s; i++){
        for(int j = 0; j < sz(anc[x[i]]); j++)
            ans[anc[x[i]][j].fi] = min(ans[anc[x[i]][j].fi], anc[x[i]][j].sc);
    }

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

    for(int i = 0; i < s; i++)
        for(int j = 0; j < sz(anc[x[i]]); j++)ans[anc[x[i]][j].fi] = INF;

  return resp;
}

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