이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <memory>
#include <vector>
#define int int64_t
using namespace std;
int log2(int n)
{
int res = 0;
for (; n; n >>= 1) res++;
return res;
}
struct graph
{
vector<vector<pair<int,int>>> adjlist;
vector<vector<int>> lcatable;
vector<int> lvl;
vector<int> submxdist;
vector<int> premx;
vector<int> premxdist;
vector<bool> shop;
int n;
int logn;
int rt;
int dfs(int curr, int par, int pm, int pmd, int lv)
{
lvl[curr] = lv;
lcatable[0][curr] = par;
premx[curr] = pm;
premxdist[curr] = pmd;
if (shop[curr])
{
premxdist[curr] = 0;
premx[curr] = curr;
}
int md = 1e15;
for (auto p : adjlist[curr])
{
int next = p.first;
if (next == par) continue;
md = min(md, p.second + dfs(next, curr, premx[curr], premxdist[curr] + p.second, lv + 1));
}
submxdist[curr] = md;
return (shop[curr] ? 0 : md);
}
void build()
{
logn = log2(n);
lcatable.resize(logn, vector<int>(n - 1));
premx.resize(n, -1);
submxdist.resize(n, 1e14);
premxdist.resize(n, 1e14);
lvl.resize(n);
dfs(rt, -1, rt, 0, 0);
for (int l = 1; l < logn; l++)
{
for (int i = 0; i < n; i++)
{
lcatable[l][i] = (lcatable[l - 1][i] == -1 ? -1 : lcatable[l - 1][lcatable[l - 1][i]]);
}
}
}
int lca(int a, int b)
{
if (lvl[a] < lvl[b]) swap(a, b);
int ld = lvl[a] - lvl[b];
int e = 1;
for (int i = 0; i < logn; i++)
{
if (ld & e) a = lcatable[i][a];
e *= 2;
}
if (a == b) return a;
for (int i = logn - 1; i >= 0; i--)
{
if (lcatable[i][a] != lcatable[i][b])
{
a = lcatable[i][a];
b = lcatable[i][b];
}
}
return lcatable[0][a];
}
void print()
{
for (auto i : lvl) cout << i << " ";
cout << "\n";
for (auto i : submxdist) cout << i << " ";
cout << "\n";
for (auto i : premx) cout << i << " ";
cout << "\n";
for (auto i : premxdist) cout << i << " ";
cout << "\n";
}
};
signed main()
{
int n, s, q, e;
cin >> n >> s >> q >> e;
graph g;
g.n = n;
g.adjlist.resize(n);
g.shop.resize(n, false);
g.rt = e - 1;
vector<pair<int,int>> edges;
for (int i = 0; i < n - 1; i++)
{
int a, b, w;
cin >> a >> b >> w;
a--; b--;
g.adjlist[a].emplace_back(b, w);
g.adjlist[b].emplace_back(a, w);
edges.emplace_back(a, b);
}
for (int i = 0; i < s; i++)
{
int p;
cin >> p;
p--;
g.shop[p] = true;
}
g.build();
// g.print();
for (int i = 0; i < q; i++)
{
//cerr << "Ok\n";
int ed, ps;
cin >> ed >> ps;
ed--; ps--;
// cerr << "Ok\n";
pair<int,int> e = edges[ed];
// cerr << "Ok\n";
if (g.lvl[e.first] > g.lvl[e.second]) swap(e.first, e.second);
if (g.lca(e.second, ps) != e.second)
{
cout << "escaped\n";
continue;
}
int mmin = g.submxdist[ps];
if (g.lvl[e.first] < g.lvl[ps]) mmin = min(mmin, g.premxdist[ps]);
if (mmin >= 1e15) cout << "oo\n";
else cout << mmin << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |