QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#391989#4408. 燃烧的呐球bachbeo2007100 ✓9564ms377052kbC++2311.3kb2024-04-16 23:57:412024-04-16 23:57:42

Judging History

This is the latest submission verdict.

  • [2024-04-16 23:57:42]
  • Judged
  • Verdict: 100
  • Time: 9564ms
  • Memory: 377052kb
  • [2024-04-16 23:57:41]
  • Submitted

answer

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define ll long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e9;
const int mod=998244353;
const int maxn=1000005;
const int B=650;
const int maxs=655;
const int maxm=100005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
const int base=101;

int n,m,t;
int L[maxn],R[maxn],num[maxn],T;
vector<int> edge[maxn];
vector<int> pos[maxn];
int X[maxm],Y[maxm];

void pre_dfs(int u){
    L[u]=++T;
    for(int v:edge[u]) pre_dfs(v);
    R[u]=T;num[u]=R[u]-L[u]+1;
}

int par[maxm],cnt;
long long total=0;
int findpar(int u){
    if(u!=par[u]) return par[u]=findpar(par[u]);
    return u;
}
bool unions(int u,int v){
    u=findpar(u);v=findpar(v);
    if(u==v) return false;
    return cnt++,par[v]=u,true;
}

struct node{
    pii a={inf,-1},b={inf,-1};
    node(){};
    void add(pii x){
        if(x<a){
            if(x.se!=a.se) b=a;
            a=x;
        }
        else if(x<b && x.se!=a.se) b=x;
    }
};

void merge(node &res,node &a,node &b){
    res=a;
    res.add(b.a);
    res.add(b.b);
}

pii Min[maxm];
void Add(int id,int val,int cc){
    if(findpar(cc)!=findpar(id)) Min[id]=min(Min[id],{val,cc});
}

namespace S1{
    int C[maxn],S;
    void reset(){
        S=0;
        for(int i=0;i<=n;i++) C[i]=0;
    }
    void addnum(int x){
        C[x]=1;
    }
    void compress(){
        for(int i=1;i<=n;i++) C[i]+=C[i-1];
        S=C[n];
    }

    node res;
    node tree[4*maxm];
    void build(int l=1,int r=S,int id=1){
        tree[id]=node();
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    }
    void update(int l,int r,int id,int p,pii val){
        tree[id].add(val);
        if(l==r) return;
        int mid=(l+r)>>1;
        if(p<=mid) update(l,mid,id<<1,p,val);
        else update(mid+1,r,id<<1|1,p,val);
    }
    void update(int p,pii val){
        if(C[p]) update(1,S,1,C[p],val);
    }

    void query(int l,int r,int id,int tl,int tr){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr) return merge(res,res,tree[id]);
        int mid=(l+r)>>1;
        query(l,mid,id<<1,tl,tr);query(mid+1,r,id<<1|1,tl,tr);
    }
    node query(int l,int r){
        res=node();
        if(C[l-1]<C[r]) query(1,S,1,C[l-1]+1,C[r]);
        return res;
    }
}

namespace S2{
    int C[maxn],S;
    void reset(){
        S=0;
        for(int i=0;i<=n;i++) C[i]=0;
    }
    void addnum(int x){
        C[x]=1;
    }
    void compress(){
        for(int i=1;i<=n;i++) C[i]+=C[i-1];
        S=C[n];
    }

    node res;
    vector<node> tree[4*maxm];
    void build(int l=1,int r=S,int id=1){
        tree[id]={node()};
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    }

    void update(int l,int r,int id,int p,pii val){
        if(val.se!=-1){
            tree[id].emplace_back(tree[id].back());
            tree[id].back().add(val);
        }
        else tree[id].pop_back();
        if(l==r) return;
        int mid=(l+r)>>1;
        if(p<=mid) update(l,mid,id<<1,p,val);
        else update(mid+1,r,id<<1|1,p,val);
    }
    void update(int p,pii val){
        if(C[p]) update(1,S,1,C[p],val);
    }

    void query(int l,int r,int id,int tl,int tr){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr) return merge(res,res,tree[id].back());
        int mid=(l+r)>>1;
        query(l,mid,id<<1,tl,tr);query(mid+1,r,id<<1|1,tl,tr);
    }
    node query(int l,int r){
        res=node();
        if(C[l-1]<C[r]) query(1,S,1,C[l-1]+1,C[r]);
        return res;
    }

    void update(int l,int r,int id,int tl,int tr,pii val){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr){
            if(val.se!=-1){
                tree[id].emplace_back(tree[id].back());
                tree[id].back().add(val);
            }
            else tree[id].pop_back();
            return;
        }
        int mid=(l+r)>>1;
        update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
    }
    void update(int l,int r,pii val){
        if(C[l-1]<C[r]) update(1,S,1,C[l-1]+1,C[r],val);
    }

    void query(int l,int r,int id,int p){
        merge(res,res,tree[id].back());
        if(l==r) return;
        int mid=(l+r)>>1;
        if(p<=mid) return query(l,mid,id<<1,p);
        else return query(mid+1,r,id<<1|1,p);
    }
    node query(int p){
        res=node();
        if(C[p]) query(1,S,1,C[p]);
        return res;
    }
}

void dfs(int u,node cc){
    for(int id:pos[u]){
        int v=Y[id];
        cc.add({num[u]+num[v],findpar(id)});
        S2::update(L[v],{num[u]-num[v],findpar(id)});
    }
    for(int id:pos[u]){
        int v=Y[id];
        Add(id,cc.a.fi-num[u]+num[v],cc.a.se);
        Add(id,cc.b.fi-num[u]+num[v],cc.b.se);

        node cur=S2::query(L[v],R[v]);
        Add(id,cur.a.fi-num[u]+num[v],cur.a.se);
        Add(id,cur.b.fi-num[u]+num[v],cur.b.se);
    }
    for(int v:edge[u]) dfs(v,cc);
    for(int id:pos[u]){
        int v=Y[id];
        S2::update(L[v],{-1,-1});
        S1::update(L[u],{-num[u]+num[v],findpar(id)});
    }
    node cur=S1::query(L[u],R[u]);
    for(int id:pos[u]){
        int v=Y[id];
        Add(id,cur.a.fi+num[u]+num[v],cur.a.se);
        Add(id,cur.b.fi+num[u]+num[v],cur.b.se);
    }
}

void dfs3(int u){
    for(int id:pos[u]){
        int v=Y[id];
        S2::update(L[v],R[v],{num[u]+num[v],findpar(id)});
    }
    for(int id:pos[u]){
        int v=Y[id];
        node cc=S2::query(L[v]);
        Add(id,cc.a.fi-num[u]-num[v],cc.a.se);
        Add(id,cc.b.fi-num[u]-num[v],cc.b.se);
    }
    for(int v:edge[u]) dfs3(v);
    for(int id:pos[u]){
        int v=Y[id];
        S2::update(L[v],R[v],{-1,-1});
    }
}

namespace S3{
    int C[maxn],S;
    void reset(){
        S=0;
        for(int i=0;i<=n;i++) C[i]=0;
    }
    void addnum(int x){
        C[x]=1;
    }
    void compress(){
        for(int i=1;i<=n;i++) C[i]+=C[i-1];
        S=C[n];
    }

    vector<int> query[4*maxm],val[4*maxm];
    void update(int l,int r,int id,int tl,int tr,int x){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr){
            query[id].push_back(x);
            return;
        }
        int mid=(l+r)>>1;
        update(l,mid,id<<1,tl,tr,x);update(mid+1,r,id<<1|1,tl,tr,x);
    }
    void update(int l,int r,int x){
        if(C[l-1]<C[r]) update(1,S,1,C[l-1]+1,C[r],x);
    }
    void add(int l,int r,int id,int p,int x){
        val[id].push_back(x);
        if(l==r) return;
        int mid=(l+r)>>1;
        if(p<=mid) add(l,mid,id<<1,p,x);
        else add(mid+1,r,id<<1|1,p,x);
    }
    void add(int p,int x){
        if(C[p]) add(1,S,1,C[p],x);
    }
    void build(){
        for(int i=1;i<=4*S;i++){
            if(val[i].empty()) continue;
            vector<pair<int,node>> cur;
            int j=0;
            for(int id:query[i]){
                while(j<(int)val[i].size() && L[Y[val[i][j]]]<=R[Y[id]]){
                    int p=val[i][j++];
                    node cc=node();
                    cc.add({-num[X[p]]-num[Y[p]],findpar(p)});
                    cur.push_back({L[Y[p]],cc});
                }
                while((int)cur.size()>=2 && cur.end()[-2].fi>=L[Y[id]]){
                    node cc=cur.back().se;cur.pop_back();
                    merge(cur.back().se,cur.back().se,cc);
                }
                node cc;
                if(!cur.empty() && cur.back().fi>=L[Y[id]]) cc=cur.back().se;
                else cc=node();
                int u=X[id],v=Y[id];
                Add(id,cc.a.fi+num[u]+num[v],cc.a.se);
                Add(id,cc.b.fi+num[u]+num[v],cc.b.se);
            }
        }
    }
}

void print(){
    for(int i=1;i<=m;i++){
        cout << i << ' ' << Min[i].fi << ' ' << Min[i].se << '\n';
    }
    cout << '\n';
}

void cal(){
    S1::reset();
    S2::reset();
    for(int i=1;i<=n;i++) pos[i].clear();
    for(int i=1;i<=m;i++){
        pos[X[i]].push_back(i);
        S1::addnum(L[X[i]]);
        S2::addnum(L[Y[i]]);
    }
    S1::compress();
    S2::compress();
    S1::build();
    S2::build();
    dfs(1,node());
    //print();
    if(!t){
        node cur=node();
        for(int i=1;i<=m;i++) cur.add({num[X[i]]+num[Y[i]],findpar(i)});
        for(int i=1;i<=m;i++){
            Add(i,num[X[i]]+num[Y[i]]+cur.a.fi,cur.a.se);
            Add(i,num[X[i]]+num[Y[i]]+cur.b.fi,cur.b.se);
        }
        dfs3(1);
        //print();
        S3::build();
    }
    //print();
}

void solve(){
    cin >> n >> m;
    for(int i=2;i<=n;i++){
        int p;cin >> p;
        edge[p].push_back(i);
    }
    pre_dfs(1);
    for(int i=1;i<=m;i++){
        cin >> X[i] >> Y[i];
        par[i]=i;
    }

    for(int i=1;i<=m;i++) S3::addnum(L[X[i]]);
    S3::compress();
    vector<int> ord(m);
    iota(ord.begin(),ord.end(),1);
    sort(ord.begin(),ord.end(),[](int a,int b){
        return L[Y[a]]<L[Y[b]];
    });
    for(int id:ord) S3::add(L[X[id]],id);
    sort(ord.begin(),ord.end(),[](int a,int b){
        if(R[Y[a]]!=R[Y[b]]) return R[Y[a]]<R[Y[b]];
        else return L[Y[a]]>L[Y[b]];
    });
    for(int id:ord) S3::update(L[X[id]],R[X[id]],id);

    while(cnt!=m-1){
        //cout << "********************************\n";
        for(int i=1;i<=m;i++) Min[i]={inf,-1};
        cal();t^=1;
        for(int i=1;i<=m;i++) swap(X[i],Y[i]);
        cal();t^=1;
        for(int i=1;i<=m;i++) swap(X[i],Y[i]);

        //print();
        for(int i=1;i<=m;i++){
            if(findpar(i)==i) continue;
            int p=findpar(i);
            Min[p]=min(Min[p],Min[i]);
        }
        for(int i=1;i<=m;i++){
            if(findpar(i)!=i) continue;
            if(unions(i,Min[i].se)){
                //cout << i << ' ' << add.se << ' ' << add.fi << '\n';
                total+=Min[i].fi;
            }
        }
    }
    cout << total << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Details

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 12ms
memory: 24628kb

Test #2:

score: 0
Accepted
time: 10ms
memory: 22632kb

Test #3:

score: 0
Accepted
time: 12ms
memory: 24560kb

Test #4:

score: 0
Accepted
time: 7ms
memory: 24580kb

Test #5:

score: 0
Accepted
time: 11ms
memory: 24496kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 2532ms
memory: 115644kb

Test #7:

score: 0
Accepted
time: 2103ms
memory: 113816kb

Test #8:

score: 0
Accepted
time: 876ms
memory: 107252kb

Test #9:

score: 0
Accepted
time: 946ms
memory: 112604kb

Test #10:

score: 0
Accepted
time: 1457ms
memory: 111412kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 3319ms
memory: 130944kb

Test #12:

score: 0
Accepted
time: 2798ms
memory: 128052kb

Test #13:

score: 0
Accepted
time: 1318ms
memory: 120856kb

Test #14:

score: 0
Accepted
time: 1759ms
memory: 125520kb

Test #15:

score: 0
Accepted
time: 2309ms
memory: 124912kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 703ms
memory: 31908kb

Test #17:

score: 0
Accepted
time: 716ms
memory: 30224kb

Test #18:

score: 0
Accepted
time: 524ms
memory: 31044kb

Test #19:

score: 0
Accepted
time: 501ms
memory: 31504kb

Test #20:

score: 0
Accepted
time: 709ms
memory: 31500kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 9373ms
memory: 375916kb

Test #22:

score: 0
Accepted
time: 9564ms
memory: 376948kb

Test #23:

score: 0
Accepted
time: 9531ms
memory: 375572kb

Test #24:

score: 0
Accepted
time: 9526ms
memory: 375872kb

Test #25:

score: 0
Accepted
time: 9530ms
memory: 377052kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1249ms
memory: 112332kb

Test #27:

score: 0
Accepted
time: 1234ms
memory: 113132kb

Test #28:

score: 0
Accepted
time: 1279ms
memory: 113876kb

Test #29:

score: 0
Accepted
time: 1269ms
memory: 114204kb

Test #30:

score: 0
Accepted
time: 1348ms
memory: 114220kb

Subtask #7:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #31:

score: 30
Accepted
time: 5691ms
memory: 155944kb

Test #32:

score: 0
Accepted
time: 4670ms
memory: 154440kb

Test #33:

score: 0
Accepted
time: 2516ms
memory: 144004kb

Test #34:

score: 0
Accepted
time: 2718ms
memory: 150148kb

Test #35:

score: 0
Accepted
time: 3523ms
memory: 151128kb

Test #36:

score: 0
Accepted
time: 5844ms
memory: 156424kb

Test #37:

score: 0
Accepted
time: 3812ms
memory: 155444kb

Test #38:

score: 0
Accepted
time: 2505ms
memory: 145792kb

Test #39:

score: 0
Accepted
time: 2637ms
memory: 149112kb

Test #40:

score: 0
Accepted
time: 3405ms
memory: 149552kb