QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#161142#7103. Red Black Treeucup-team139#AC ✓1546ms29776kbC++233.4kb2023-09-02 22:36:592023-09-02 22:37:00

Judging History

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

  • [2023-09-02 22:37:00]
  • 评测
  • 测评结果:AC
  • 用时:1546ms
  • 内存:29776kb
  • [2023-09-02 22:36:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100'005, LOGN = 17;
long long dist[MAXN],dist2[MAXN];
vector<pair<int,long long>> grafo[MAXN];
int n,m,q,par[MAXN][LOGN],prof[MAXN],ndist[MAXN];
bool red[MAXN];
vector<long long> tmpdist;

void dfs2(int nodo,int last,long long val,int lastred,long long val2=0){
    if(red[nodo])val=0,lastred=nodo;
    dist[nodo]=val;
    dist2[nodo]=val2;
    ndist[nodo]=lastred;
    tmpdist.push_back(val);
    
    for(auto [to,cost] : grafo[nodo]){
        if(to!=last){
            dfs2(to,nodo,val+cost,lastred,val2+cost);
        }
    }
}

void dfs(int nodo=0, int last=0, int p=0){
    par[nodo][0]=last;
    prof[nodo]=p;
    for(auto &[x,cost] : grafo[nodo]){
        if(x!=last){
            dfs(x,nodo,p+1);
        }
    }
}

int lca(int x,int y){
    if(x==y)return x;
    if(prof[x]>prof[y])swap(x,y);
    for(int i=LOGN-1;i>=0;i--){
        if(prof[par[y][i]]>=prof[x]){
            y=par[y][i];
        }
    }
    if(x==y)return x;
    for(int i=LOGN-1;i>=0;i--){
        if(par[x][i]!=par[y][i]){
            x=par[x][i];
            y=par[y][i];
        }
    }
    return par[x][0];
}

int calc(int nodo,long long bound){
    int res=nodo;
    if(red[nodo])return nodo;
    
    for(int i=LOGN-1;i>=0;i--){
        if(prof[par[nodo][i]]>=prof[ndist[nodo]] && dist[nodo]-dist[par[nodo][i]]<=bound){
            bound-=dist[nodo]-dist[par[nodo][i]];
            nodo = par[nodo][i];
        }
    }
    
    return nodo;
}

bool comp(int x,int y){
    return dist[x]>dist[y];
}

void solve(int t){
    cin>>n>>m>>q;
    
    for(int i=0;i<=n;i++){
        red[i]=false;
        grafo[i].clear();
        dist[i]=0;
        ndist[i]=0;
        dist2[i]=0;
    }
    
    for(int i=0;i<m;i++){
        int r;
        cin>>r;
        red[r]=true;
    }
    for(int i=0;i<n-1;i++){
        int u,v,w;
        cin>>u>>v>>w;
        grafo[u].emplace_back(v,w);
        grafo[v].emplace_back(u,w);
    }
    tmpdist.clear();
    grafo[0].push_back({1,0});
    dfs();
    dfs2(1,-1,0,1);
    
    sort( tmpdist.begin(), tmpdist.end() );
    tmpdist.erase( unique( tmpdist.begin(), tmpdist.end() ), tmpdist.end() );
    
    for(int j=1;j<LOGN;j++){
        for(int i=0;i<=n;i++)
            par[i][j]=par[par[i][j-1]][j-1];
    }
    
    while(q--){
        int k;
        cin>>k;
        vector<int> nod(k),curr(k);
        for(int i=0;i<k;i++){
            cin>>nod[i];
        }
        
        sort(nod.begin(),nod.end(),comp);
        
        for(int i=0;i<k;i++){
            if(i==0)curr[i]=nod[i];
            else curr[i]=lca(curr[i-1],nod[i]);
        }
        
        int low = 0, up = k-1, mid;
        while(up-low>1){
            mid=(up+low)/2;
            
            long long maxi=0;
            for(int i=0;i<=mid;i++){
                maxi=max(maxi,dist2[nod[i]]-dist2[curr[mid]]);
            }
            
            if(maxi<=dist[nod[mid+1]])low=mid;
            else up=mid;
        }
        
        long long s1=dist[nod[low+1]];
        long long s2=0;
        for(int i=0;i<=up;i++){
            s2=max(s2,dist2[nod[i]]-dist2[curr[up]]);
        }
        
        cout<<min(s1,s2)<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9740kb

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: 1546ms
memory: 29776kb

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