| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1087091 | quangminh412 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
/*
John Watson
https://codeforces.com/profile/quangminh98
Mua Code nhu mua Florentino !!
*/
#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const int maxn = 2e5 + 9;
vector<int> adj[maxn];
int sz[maxn], par[20][maxn], h[maxn], tp[maxn], id[maxn];
ll val[maxn];
int n;
ll k;
//
ll st[4 * maxn];
void update(int head, int l, int r, int pos, ll val)
{
if (l == r)
{
st[head] = val;
return;
}
int mid = l + r >> 1;
if (pos <= mid)
update(2 * head, l, mid, pos, val);
else
update(2 * head + 1, mid + 1, r, pos, val);
st[head] = st[2 * head] + st[2 * head + 1];
}
void update(int pos, ll val) { update(1, 1, n, pos, val); }
ll query(int head, int l, int r, int u, int v)
{
if (l > v || r < u) return 0ll;
if (u <= l && r <= v) return st[head];
int mid = l + r >> 1;
return query(2 * head, l, mid, u, v) + query(2 * head + 1, mid + 1, r, u, v);
}
ll query(int u, int v) { return query(1, 1, n, u, v); }
//
void DFS(int u, int p = -1)
{
sz[u] = 1;
for (int v : adj[u])
{
if (v == p) continue;
h[v] = h[u] + 1;
par[0][v] = u;
for (int i = 1; i < 20; i++)
par[i][v] = par[i - 1][par[i - 1][v]];
DFS(v, u);
sz[u] += sz[v];
}
}
int LCA(int u, int v)
{
if (h[u] < h[v]) swap(u, v);
int k = h[u] - h[v];
for (int i = 0; i < 20; i++)
if (k >> i & 1)
u = par[i][u];
if (u == v) return u;
for (int i = 19; i >= 0; i--)
if (par[i][u] != par[i][v])
{
u = par[i][u];
v = par[i][v];
}
return par[0][u];
}
int timeDFS = 0;
void HLD(int u, int p, int head)
{
id[u] = ++timeDFS;
tp[u] = head;
update(id[u], val[u]);
int nxt = -1;
for (int v : adj[u])
{
if (v == p) continue;
if (nxt == -1 || sz[nxt] < sz[v])
nxt = v;
}
if (nxt != -1) HLD(nxt, u, head);
for (int v : adj[u])
{
if (v == p || v == nxt) continue;
HLD(v, u, v);
}
}
ll queryPath(int u, int p)
{
ll ans = 0;
while (u != p)
if (tp[u] == u)
{
ans += query(id[u], id[u]);
u = par[0][u];
} else
if (h[tp[u]] > h[p])
{
ans += query(id[tp[u]], id[u]);
u = par[0][tp[u]];
} else
{
ans += query(id[p] + 1, id[u]);
break;
}
return ans;
}
int best_path(int _n, ll _k, int H[][2], int l[])
{
n = _n;
k = _k;
for (int i = 0; i < n; i++)
{
int u = H[i][0], v = H[i][1];
u++; v++;
adj[u].push_back(v);
adj[v].push_back(u);
}
DFS(1);
for (int i = 0; i < n; i++)
{
ll w = l[i];
int u = H[i][0], v = H[i][1];
u++; v++;
val[h[u] > h[v] ? u : v] = w;
}
HLD(1, -1, 1);
int ans = 0;
for (int u = 1; u <= n; u++)
for (int v = u + 1; v <= n; v++)
{
int lca = LCA(u, v);
ll path = query(id[lca], id[lca]) + queryPath(u, lca) + queryPath(v, lca);
if (path == k)
ans = max(ans, h[u] + h[v] - 2 * h[lca]);
}
return ans;
}