QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179987 | #7103. Red Black Tree | notyour_young | WA | 818ms | 35428kb | C++17 | 1.8kb | 2023-09-15 14:13:24 | 2023-09-15 14:13:24 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
using i64 = long long;
using PII = pair<i64, int>;
const int N = 1e5 + 10;
int n, m, q;
vector<PII> g[N];
bool red[N];
i64 fa[N][17], dep[N], dis[N], dr[N];
i64 dfn[N], cnt;
void dfs(int u, int father)
{
dfn[u] = ++ cnt;
dep[u] = dep[father] + 1;
fa[u][0] = father;
for(int k = 1;k < 17;k ++)
fa[u][k] = fa[fa[u][k - 1]][k - 1];
if(red[u])
dr[u] = 0;
for(auto [v, w] : g[u])
{
if(v == father)
continue;
dis[v] = dis[u] + w;
dr[v] = dr[u] + w;
dfs(v, u);
}
}
int lca(int a, int b)
{
if(a == -1)
return 1;
if(dep[a] < dep[b])
swap(a, b);
for(int k = 16;k >= 0;k --)
if(dep[fa[a][k]] >= dep[b])
a = fa[a][k];
if(a == b)
return a;
for(int k = 16;k >= 0;k --)
if(fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];
return fa[a][0];
}
void solve()
{
cin >> n >> m >> q;
for(int i = 1, v;i <= m;i ++)
cin >> v, red[v] = true;
for(int i = 1;i < n;i ++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
while(q --)
{
int k;
cin >> k;
vector<int> v(k);
for(int & x : v)
cin >> x;
sort(v.begin(), v.end(), [&](int a, int b) {
return dr[a] > dr[b];
});
i64 res = dr[v[0]], mx = dis[v[0]];
int anc = v[0];
for(int i = 0;i + 1 < v.size();i ++)
{
anc = lca(anc, v[i]);
mx = max(mx, dis[v[i]]);
res = min(res, max(dr[v[i + 1]], mx - dis[anc]));
}
cout << res << endl;
}
for(int i = 1;i<= n;i ++)
red[i] = false, g[i].clear();
cnt = 0;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
int tc;
cin >> tc;
while(tc --)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 6116kb
input:
2 12 2 4 1 9 1 2 1 2 3 4 3 4 3 3 5 2 2 6 2 6 7 1 6 8 2 2 9 5 9 10 2 9 11 3 1 12 10 3 3 7 8 4 4 5 7 8 4 7 8 10 11 3 4 5 12 3 2 3 1 2 1 2 1 1 3 1 1 1 2 1 2 3 1 2 3
output:
4 5 3 8 0 0 0
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 818ms
memory: 35428kb
input:
522 26 1 3 1 1 4 276455 18 6 49344056 18 25 58172365 19 9 12014251 2 1 15079181 17 1 50011746 8 9 2413085 23 24 23767115 22 2 26151339 26 21 50183935 17 14 16892041 9 26 53389093 1 20 62299200 24 18 56114328 11 2 50160143 6 26 14430542 16 7 32574577 3 16 59227555 3 15 8795685 4 12 5801074 5 20 57457...
output:
148616264 148616264 66903787 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 57081624 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164...
result:
wrong answer 3rd lines differ - expected: '0', found: '66903787'