QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#579872 | #7103. Red Black Tree | xuanbac05 | AC ✓ | 1025ms | 30052kb | C++17 | 3.1kb | 2024-09-21 18:47:46 | 2024-09-21 18:47:46 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;
const int mxN = 2e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e15 + 7;
const int base = 307;
const int LOG = 20;
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;
}
int n;
int m;
int q;
int a[mxN];
int dep[mxN];
int par[mxN][LOG + 1];
bool red[mxN];
ll dist[mxN];
pair<ll, int> best[mxN];
vector<pair<int, int>> adj[mxN];
int timer = 0;
void dfs(int u, int p, int cur = -1) {
if(red[u] == true) cur = u;
for(auto it : adj[u]) {
int v = it.fi;
int c = it.se;
if(v == p) continue;
dist[v] = dist[u] + c;
dep[v] = dep[u] + 1;
par[v][0] = u;
dfs(v, u, cur);
}
best[u] = make_pair(dist[u] - dist[cur], cur);
}
int getlca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int j = LOG; j >= 0; j--) if(dep[par[u][j]] >= dep[v]) u = par[u][j];
if(u == v) return u;
for(int j = LOG; j >= 0; j--) {
if(par[u][j] != par[v][j]) {
u = par[u][j];
v = par[v][j];
}
}
return par[u][0];
}
bool cmp(int x, int y) {
return best[x].fi > best[y].fi;
}
void solve()
{
cin >> n >> m >> q;
for(int i = 1; i <= m; i++) {
int x; cin >> x;
red[x] = true;
}
for(int i = 1; i < n; i++) {
int u, v, c;
cin >> u >> v >> c;
adj[u].pb({v, c});
adj[v].pb({u, c});
}
par[1][0] = 1;
dfs(1, -1);
for (int j = 1; j <= LOG; j++)
for (int i = 1; i <= n; i++) par[i][j] = par[par[i][j - 1]][j - 1];
while(q--) {
int k; cin >> k;
ll res = -infll;
vector<int> node;
for(int i = 1; i <= k; i++) {
int x; cin >> x;
node.pb(x);
maximize(res, best[x].fi);
}
sort(all(node), cmp);
int lca = node[0];
ll maxDist = dist[node[0]];
for(int i = 0; i < sz(node); i++) {
lca = getlca(lca, node[i]);
maximize(maxDist, dist[node[i]]);
if(i + 1 < sz(node)) minimize(res, max(maxDist - dist[lca], best[node[i + 1]].fi));
else minimize(res, maxDist - dist[lca]);
}
cout << res << endl;
}
for(int u = 1; u <= n; u++) {
adj[u].clear();
red[u] = false;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen(TASK".inp" , "r" , stdin);
// freopen(TASK".out" , "w" , stdout);
int tc = 1;
cin >> tc;
while(tc--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11880kb
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: 0
Accepted
time: 1025ms
memory: 30052kb
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 0 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 0 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164 181713164 181...
result:
ok 577632 lines
Extra Test:
score: 0
Extra Test Passed