QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215389 | #7103. Red Black Tree | ammardab3an | AC ✓ | 885ms | 60192kb | C++20 | 4.3kb | 2023-10-15 09:35:07 | 2023-10-15 09:35:07 |
Judging History
answer
// By AmmarDab3an
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define ll int64_t
// typedef unsigned int uint;
// typedef long long int ll;
// typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> iii;
typedef pair<ll, pll> lll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define freopenI freopen("input.txt", "r", stdin);
#define freopenO freopen("output.txt", "w", stdout);
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
int mul(int a, int b){
int ret = (1ll * (a%MOD) * (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int add(int a, int b){
int ret = (1ll * (a%MOD) + (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int pow_exp(int n, int p){
if(!p) return 1;
if(p&1) return mul(n, pow_exp(n, p-1));
int tmp = pow_exp(n, p/2);
return mul(tmp, tmp);
}
int inv(int x){
return pow_exp(x, MOD-2);
}
const int MAX = 2e5 + 10;
const int NMAX = 2e5 + 10;
const int MMAX = 2e5 + 10;
const int LOG_MAX = ceil(log2(double(NMAX)));
const int BLOCK = ceil(sqrt(double(NMAX)));
// int fac[NMAX], ifac[NMAX];
//
// void init(){
//
// fac[0] = 1;
// for(int i = 1; i < NMAX; i++){
// fac[i] = mul(fac[i-1], i);
// }
//
// ifac[NMAX-1] = inv(fac[NMAX-1]);
// for(int i = NMAX-2; i >= 0; i--){
// ifac[i] = mul(ifac[i+1], i+1);
// }
// }
//
// int choose(int n, int c){
// assert(n >= c);
// return mul(fac[n], mul(ifac[c], ifac[n-c]));
// }
vpii adj[NMAX];
int par[NMAX][LOG_MAX];
int dist[NMAX][LOG_MAX];
int depth[NMAX];
int val[NMAX];
void dfs(int u, int p){
for(auto [v, w] : adj[u]) if(v != p){
depth[v] = depth[u] + 1;
par[v][0] = u;
for(int i = 1; i < LOG_MAX; i++){
par[v][i] = par[par[v][i-1]][i-1];
}
dist[v][0] = w;
for(int i = 1; i < LOG_MAX; i++){
dist[v][i] = dist[v][i-1] + dist[par[v][i-1]][i-1];
}
val[v] = min(val[v], val[u] + w);
dfs(v, u);
}
}
pii lca(int u, int v){
if(u==-1){
return {v, 0};
}
if(depth[u] < depth[v]) swap(u, v);
int sm_dist = 0;
int dif = depth[u] - depth[v];
for(int i = 0; i < LOG_MAX; i++) if((dif>>i)&1){
sm_dist += dist[u][i];
u = par[u][i];
}
if(u==v){
return {u, sm_dist};
}
for(int i = LOG_MAX-1; i >= 0; i--) if(par[u][i] != par[v][i]){
sm_dist += dist[u][i] + dist[v][i];
u = par[u][i];
v = par[v][i];
}
return {par[u][0], sm_dist + dist[u][0] + dist[v][0]};
}
int32_t main(){
fastIO;
#ifdef LOCAL
freopenI;
freopenO;
#endif
// freopen("name.in", "r", stdin);
// init();
int t; cin >> t; while(t--){
int n, m, q;
cin >> n >> m >> q;
for(int i = 0; i < n; i++){
adj[i].clear();
val[i] = INFLL;
}
for(int i = 0; i < m; i++){
int u;
cin >> u;
u--;
val[u] = 0;
}
for(int i = 1; i < n; i++){
int u, v, w;
cin >> u >> v >> w;
u--, v--;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
dfs(0, -1);
while(q--){
int k;
cin >> k;
vi tmp(k);
for(auto &e : tmp) cin >> e, --e;
sort(tmp.begin(), tmp.end(), [&](int u, int v){
return val[u] > val[v];
});
// cout << ' ';
// for(auto e : tmp) cout << e << ' '; cout << endl << flush;
int mx = 0;
int u = -1;
int ans = INFLL;
for(int i = 0; i < k; i++){
int v = tmp[i];
pii g = lca(u, v);
int d0 = lca(u, g.first).second;
int d1 = lca(v, g.first).second;
mx = max(mx+d0, d1);
// cout << v+1 << ' ' << u+1 << ' ' << g.first+1 << ' ' << d << ' ' << mx << endl;
u = g.first;
int cans = mx;
if(i+1 < k) cans = max(cans, val[tmp[i+1]]);
ans = min(ans, cans);
}
cout << ans << endl;
}
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 14484kb
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: 885ms
memory: 60192kb
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