| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 878502 | cpptowin | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
int n,q;
vii ke[maxn];
int par[maxn][20],sz[maxn],h[maxn],d[maxn];
int ind[maxn],head[maxn],cnt = 1;
vii adj[maxn];
bool type[maxn];
void dfs(int u,int parent)
{
sz[u] = 1;
for(auto [v,w] : ke[u])
{
if(v == parent) continue;
par[v][0] = u;
h[v] = h[u] + 1;
d[v] = d[u] + w;
dfs(v,u);
sz[u] += sz[v];
}
}
void hld(int u,int parent)
{
if(head[cnt] == 0) head[cnt] = u;
ind[u] = cnt;
int sc = -1,maxx = -1;
for(auto [v,w] : ke[u]) if(v != parent)
{
if(maxx < sz[v])
{
maxx = sz[v];
sc = v;
}
}
if(sc != -1) hld(sc,u);
for(auto [v,w] : ke[u]) if(v != parent and v != sc)
{
cnt++;
hld(v,u);
}
}
void get(int u)
{
int val = d[u];
int uchain,vchain = ind[1];
while(1)
{
uchain = ind[u];
adj[uchain].pb(u,val);
if(uchain == vchain) return;
u = ind[u];
u = par[head[u]][0];
}
}
void Init(int N,int A[],int B[],int D[])
{
fo(i,0,n - 2)
{
int u,v,w;
u = A[i],v = B[i],w = D[i];
u++;
v++;
ke[u].pb(v,w);
ke[v].pb(u,w);
}
dfs(1,1);
fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
hld(1,1);
}
long long Query(int S,int X[],int T,int Y[])
{
int ans = 2e18;
fo(i,0,S - 1)
{
int x = X[i];
x++;
get(x);
}
fo(i,0,T - 1)
{
int x = Y[i];
x++;
type[x] = 1;
get(x);
}
fo(i,1,cnt)
{
int minn[2];
minn[0] = minn[1] = 2e18;
sort(adj[i].begin(),adj[i].end(),[](pii a,pii b)
{
return d[a.fi] > d[b.fi];
});
for(auto [v,dist] : adj[i])
{
int x = type[v];
ans = min(ans,minn[1 - x] - 2 * d[v] + dist);
minn[x] = min(minn[x],dist);
}
}
fo(i,1,cnt) adj[i].clear();
fo(i,0,T - 1) type[Y[i]] = 0;
return ans;
}