QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#158319#7103. Red Black Treeucup-team1134#AC ✓1753ms43168kbC++176.3kb2023-09-02 16:25:222023-09-02 16:25:39

Judging History

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

  • [2023-09-02 16:25:39]
  • 评测
  • 测评结果:AC
  • 用时:1753ms
  • 内存:43168kb
  • [2023-09-02 16:25:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=100005,INF=1<<30;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


// https://beet-aizu.github.io/library/tree/auxiliarytree.cpp.html

//BEGIN CUT HERE
struct LowestCommonAncestor{
    int h;
    vector< vector<int> > G,par;
    vector<int> dep;
    LowestCommonAncestor(int n):G(n),dep(n){
        h=1;
        while((1<<h)<=n) h++;
        par.assign(h,vector<int>(n,-1));
    }
    
    void add_edge(int u,int v){
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    
    void dfs(int v,int p,int d){
        par[0][v]=p;
        dep[v]=d;
        for(int u:G[v])
            if(u!=p) dfs(u,v,d+1);
    }
    
    void build(int r=0){
        int n=G.size();
        dfs(r,-1,0);
        for(int k=0;k+1<h;k++)
            for(int v=0;v<n;v++)
                if(~par[k][v])
                    par[k+1][v]=par[k][par[k][v]];
    }
    
    int lca(int u,int v){
        if(dep[u]>dep[v]) swap(u,v);
        for(int k=0;k<h;k++)
            if((dep[v]-dep[u])>>k&1)
                v=par[k][v];
        
        if(u==v) return u;
        
        for(int k=h-1;k>=0;k--)
            if(par[k][u]!=par[k][v])
                u=par[k][u],v=par[k][v];
        
        return par[0][u];
    }
    
    int distance(int u,int v){
        return dep[u]+dep[v]-dep[lca(u,v)]*2;
    }
};

//BEGIN CUT HERE
struct AuxiliaryTree : LowestCommonAncestor{
    using super = LowestCommonAncestor;
    
    vector<int> idx;
    vector<vector<int>> T;
    AuxiliaryTree(int n):super(n),idx(n),T(n){}
    
    void dfs(int v,int p,int &pos){
        idx[v]=pos++;
        for(int u:G[v])
            if(u!=p) dfs(u,v,pos);
    }
    
    void build(int r=0){
        super::build(r);
        int pos=0;
        dfs(r,-1,pos);
    }
    
    void add_aux_edge(int u,int v){
        T[u].emplace_back(v);
        T[v].emplace_back(u);
    }
    
    using super::lca, super::dep;
    void query(vector<int> &vs){
        assert(!vs.empty());
        sort(vs.begin(),vs.end(),
             [&](int a,int b){return idx[a]<idx[b];});
        vs.erase(unique(vs.begin(),vs.end()),vs.end());
        
        int k=vs.size();
        stack<int> st;
        st.emplace(vs[0]);
        for(int i=0;i+1<k;i++){
            int w=lca(vs[i],vs[i+1]);
            if(w!=vs[i]){
                int l=st.top();st.pop();
                while(!st.empty() and dep[w]<dep[st.top()]){
                    add_aux_edge(st.top(),l);
                    l=st.top();st.pop();
                }
                if(st.empty() or st.top()!=w){
                    st.emplace(w);
                    vs.emplace_back(w);
                }
                add_aux_edge(w,l);
            }
            st.emplace(vs[i+1]);
        }
        
        while(st.size()>1){
            int c=st.top();st.pop();
            add_aux_edge(st.top(),c);
        }
    }
    
    void clear(const vector<int> &ws){
        for(int w:ws) T[w].clear();
    }
};

vector<pair<int,ll>> G[MAX];
ll dis[MAX],D[MAX];

void make(int u,int p){
    for(auto [to,co]:G[u]){
        if(to==p) continue;
        if(dis[to]==0){
            
        }else{
            dis[to]=dis[u]+co;
        }
        D[to]=D[u]+co;
        make(to,u);
    }
}

int par[MAX];

void mk(int u,int p,AuxiliaryTree &T){
    par[u]=p;
    for(int to:T.T[u]){
        if(to==p) continue;
        mk(to,u,T);
    }
}

bool seen[MAX],imp[MAX];

void DFS(int u,int p,int x,ll &ma,AuxiliaryTree &T,multiset<ll> &SE){
    if(seen[u]) return;
    seen[u]=true;
    if(imp[u]){
        if(D[u]-D[x]==dis[u]-dis[x]){
            SE.erase(SE.find(dis[u]));
            chmax(ma,D[u]);
        }
    }
    for(int to:T.T[u]){
        if(to==par[u]) continue;
        DFS(to,u,x,ma,T,SE);
    }
}

ll solve(vector<int> st,vector<int> use,AuxiliaryTree &T){
    vector<pair<ll,int>> di;
    for(int i=0;i<si(use);i++){
        di.push_back(mp(dis[use[i]],use[i]));
    }
    sort(all(di));
    if(di.back().fi==0) return 0LL;
    
    for(int x:use) imp[x]=true;
    int v=di.back().se;
    multiset<ll> SE;
    ll ma=0;
    for(auto [d,x]:di) SE.insert(d);
    ll ans=(*SE.rbegin());
    
    int ro=st[0];
    for(int x:st){
        if(T.idx[ro]>T.idx[x]) ro=x;
    }
    
    mk(ro,-1,T);
    
    while(v!=-1){
        DFS(v,-1,v,ma,T,SE);
        ll re=-1;
        if(si(SE)) chmax(re,(*SE.rbegin()));
        chmax(re,ma-D[v]);
        chmin(ans,re);
        
        int p=par[v];
        if(p==-1||D[v]-D[p]!=dis[v]-dis[p]){
            break;
        }else{
            v=par[v];
        }
    }
    
    for(int x:use) imp[x]=false;
    for(int x:st) seen[x]=false;
    
    return ans;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int QQ;cin>>QQ;
    while(QQ--){
        int N,M,Q;cin>>N>>M>>Q;
        for(int i=0;i<N;i++){
            G[i].clear();
            dis[i]=1LL<<60;
            D[i]=1LL<<60;
        }
        D[0]=0;
        for(int i=0;i<M;i++){
            int x;cin>>x;x--;
            dis[x]=0;
        }
        AuxiliaryTree T(N);
        for(int i=0;i<N-1;i++){
            int a,b;cin>>a>>b;a--;b--;
            ll c;cin>>c;
            T.add_edge(a,b);
            G[a].push_back(mp(b,c));
            G[b].push_back(mp(a,c));
        }
        T.build();
        make(0,-1);
        
        while(Q--){
            int K;cin>>K;
            vector<int> st(K),use;
            for(int i=0;i<K;i++){
                int x;cin>>x;x--;
                st[i]=x;
            }
            use=st;
            T.query(st);
            
            cout<<solve(st,use,T)<<"\n";
            
            T.clear(st);
        }
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1753ms
memory: 43168kb

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