QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#459812#7103. Red Black TreeAlishAC ✓849ms31832kbC++172.4kb2024-06-30 13:41:522024-06-30 13:41:53

Judging History

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

  • [2024-06-30 13:41:53]
  • 评测
  • 测评结果:AC
  • 用时:849ms
  • 内存:31832kb
  • [2024-06-30 13:41:52]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7;

const int N = 1e5+23, L=23;

vector<pll> g[N];
int par[N][L], h[N];
ll cost[N], d[N];
int is[N];
int n, m, q;

void dfs(int v, int p=0){
    if(is[v]) cost[v]=0;
    for (auto pp: g[v]){
        int u=pp.F, w=pp.S;
        if(u==p) continue;
        par[u][0]=v;
        h[u]=h[v]+1;
        cost[u]=cost[v]+w;
        d[u]=d[v]+w;
        dfs(u, v);
    }
}

int LCA(int v, int u){
    if(h[v]>h[u]) swap(u, v);
    int d=h[u]-h[v];
    for (int i=0; i<L; i++) if(d>>i&1) u=par[u][i];
    if(v==u) return v;
    for (int i=L-1; i>=0; i--)if(par[u][i]!=par[v][i]){
        v=par[v][i];
        u=par[u][i];
    }
    return par[u][0];
}

void C(){
    for (int i=0; i<=n; i++){
        g[i].clear();
        h[i]=0;
        is[i]=0;
        cost[i]=0;
        d[i]=0;
        for (int j=0; j<L; j++) par[i][j]=0;
    }
}

int main()
{
    fast_io
    int T; cin>>T;
    while(T--){

        cin>>n>>m>>q;
        for (int i=0; i<m; i++){
            int v; cin>>v;
            is[v]=1;
        }
        for (int i=0; i<n-1; i++){
            int v, u, w; cin>>v>>u>>w;
            g[v].pb({u, w}); g[u].pb({v, w});
        }
        dfs(1);
        for (int j=1; j<L; j++)for(int i=1; i<=n; i++) par[i][j]=par[par[i][j-1]][j-1];
        while(q--){
            int k; cin>>k;
            vector<pll> vec;
            for (int i=0; i<k; i++){
                int v; cin>>v;
                vec.pb({cost[v], v});
            }
            if(k==1){ cout<<0<<endl; continue; }
            sort(all(vec)); reverse(all(vec)); vec.pb({0, 0});
            ll ans=vec[1].F, Mxd=d[vec[0].S], u=vec[0].S;
            for (int i=1; i<k; i++){
                u=LCA(u, vec[i].S);
                Mxd=max(Mxd, d[vec[i].S]);
                ans=min(ans, max(vec[i+1].F, Mxd-d[u]));
            }

            cout<<ans<<endl;
        }
        C();
    }

}

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

详细

Test #1:

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

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: 849ms
memory: 31832kb

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