| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 993710 | gortomi | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "factories.h"
#define int long long
//#include "grader.cpp"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<vector<pii> > g;
vector<bool> vis;
vector<int> s;
vector<vector<ll> > d;
vector<vector<int> > pa;
vector<ll> mini;
void calc(int v, int p)
{
s[v] = 1;
for(auto [x, w] : g[v])
{
if(vis[x]) continue;
if(x == p) continue;
calc(x, v);
s[v] += s[x];
}
}
int findc(int v, int p, int bp)
{
for(auto [x, w] : g[v])
{
if(x == p || vis[x]) continue;
if(s[bp] / 2 < s[x]) return findc(x, v, bp);
}
return v;
}
void calc2(int v, int p, ll dep, int l, int bp)
{
pa[v][l] = bp;
d[v][l] = dep;
for(auto [x, w] : g[v])
{
if(x == p || vis[x]) continue;
calc2(x, v, dep + w, l, bp);
}
}
void dec(int v, int l)
{
calc(v, 0);
int c = findc(v, 0, v);
vis[c] = 1;
calc2(c, 0, 0, l, c);
for(auto [x, w] : g[c])
{
if(!vis[x]) dec(x, l + 1);
}
}
ll Query(int t, int b[], int s, int a[])
{
vector<int> ve;
for(int i = 0; i < s; i++)
{
int x = a[i];
for(int j = 0; j < 20; j++)
{
int v = pa[x][j];
if(v != 0)
{
mini[v] = min(mini[v], d[x][j]);
ve.push_back(v);
}
}
}
ll ans = 1e15;
for(int i = 0; i < t; i++)
{
int x = b[i];
ll act = 1e15;
for(int j = 0; j < 20; j++)
{
int v = pa[x][j];
if(v != 0)
{
act = min(act, mini[v] + d[x][j]);
}
}
ans = min(act, ans);
}
for(auto x : ve) mini[x] = 1e15;
return ans;
}
void Init(int n, int a[], int b[], int c[])
{
ios::sync_with_stdio(0);
cin.tie(0);
/*int n, q;
cin >> n >> q;*/
g.resize(n);
vis.resize(n);
s.resize(n);
d.resize(n, vector<ll>(20));
pa.resize(n, vector<int>(20));
mini.resize(n, 1e15);
for(int i = 0; i < n - 1; i++)
{
int x = a[i], y = b[i], w = c[i];
/*int x, y, w;
cin >> x >> y >> w;*/
g[x].push_back({y, w});
g[y].push_back({x, w});
}
dec(1, 0);
/*while(q--)
{
int s, t;
cin >> s >> t;
int a[s], b[t];
for(int i = 0; i < s; i++) cin >> a[i];
for(int i = 0; i < t; i++) cin >> b[i];
cout << Query(s, a, t, b) << "\n";
}*/
}