QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#170435#7103. Red Black Treekjhhjki#AC ✓528ms30680kbC++202.2kb2023-09-09 15:15:502023-09-09 15:15:51

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 15:15:51]
  • 评测
  • 测评结果:AC
  • 用时:528ms
  • 内存:30680kb
  • [2023-09-09 15:15:50]
  • 提交

answer

#include <bits/stdc++.h>
#define MAXN 100005  
#define For(I,A,B) for(int I = A, endi = B; I <= endi; ++I)
#define foR(I,A,B) for(int I = A, endi = B; I >= endi; --I)
using namespace std;
typedef long long _ll;

struct Edge{ int to,nxt; _ll w; } e[MAXN<<1];
int head[MAXN],tot;
void add(int u, int v, int w)
{
    e[++tot].to = v;
    e[tot].nxt = head[u];
    e[tot].w = w;
    head[u] = tot;
}

bool red[MAXN];
_ll dis[MAXN], cost[MAXN];
int cnt, dfn[MAXN];
int pre[22][MAXN<<1],log2n[MAXN<<1^1];
int T,n,m,q,u,v,w,t,LCA;
_ll mx,ans;
inline bool cmp(int x,int y){ return cost[x] > cost[y]; }
void dfs(int u, int p)
{
    pre[0][++cnt] = u; dfn[u] = cnt;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == p) continue;
        dis[v] = dis[u] + e[i].w;
        if(red[v]) cost[v] = 0;
        else cost[v] = cost[u] + e[i].w;
        dfs(v,u);
        pre[0][++cnt] = u;
    }
}
void init()
{
    For(i,1,20)
        for(int j = 1; j + (1<<i) - 1 <= cnt; ++j)
        {
            int k = j + (1<<(i-1));
            if(dis[pre[i-1][j]] < dis[pre[i-1][k]]) pre[i][j] = pre[i-1][j];
            else pre[i][j] = pre[i-1][k];
        }
}
int lca(int x, int y)
{
    if(dfn[x] > dfn[y]) swap(x,y);
    int k = log2n[dfn[y]-dfn[x]+1], a = pre[k][dfn[x]], b = pre[k][dfn[y]-(1<<k)+1];
    return dis[a] < dis[b] ? a : b;
}
void solve()
{
    cin >> n >> m >> q; cnt = tot = 0;
    For(i,1,n) head[i] = red[i] = 0;
    For(i,1,m) cin >> u, red[u] = 1;
    For(i,2,n) cin >> u >> v >> w, add(u,v,w), add(v,u,w);
    dfs(1,0); init();
    while(q--)
    {
        vector<int> vec;
        cin >> t;
        while(t--) cin >> u, vec.push_back(u); vec.push_back(0);
        sort(vec.begin(),vec.end(),cmp);
        LCA = vec[0]; mx = dis[vec[0]]; ans = cost[vec[1]];
        For(i,1,vec.size()-2)
        {
            LCA = lca(LCA,vec[i]);
            mx = max(mx,dis[vec[i]]);
            ans = min(ans,max(mx-dis[LCA],cost[vec[i+1]]));
        }
        cout << ans << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    log2n[1] = 0;
    For(i,2,(MAXN<<1)-5) log2n[i] = log2n[i>>1] + 1;
    cin >> T;
    while(T--) solve();
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 12600kb

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: 528ms
memory: 30680kb

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