Submission #1014148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014148		Warinchai	JOI tour (JOI24_joitour)	C++17	0 / 100	78 ms	85532 KiB

joitour

#include "joitour.h"
#include<bits/stdc++.h>
using namespace std;
struct info{
    long long t1,t3,s1,s3,ans,chsz;
    info(long long _t1=0,long long _t3=0,long long _s1=0,long long _s3=0,long long _ans=0,long long _chsz=0){
        t1=_t1,t3=_t3,s1=_s1,s3=_s3,ans=_ans,chsz=_chsz;
    }
    friend info operator+(info a,info b){
        info c;
        c.t1=a.t1+b.t1;
        c.t3=a.t3+b.t3;
        c.s1=a.s1+b.s1+a.chsz*b.t1;
        c.s3=a.s3+b.s3+a.chsz*b.t3;
        c.ans=a.ans+b.ans+a.t1*b.s3+a.t3*b.s1+b.t1*a.s3+b.t3*a.s1;
        c.chsz=a.chsz+b.chsz;
        return c;
    }
};
info datas[800005];
struct stttree{
    int hv[800005],type[800005],l[800005],r[800005],p[800005],id,n,rt;
    vector<vector<int>>adj;
    int dfs(int u,int p){
        int sz=1,mx=0;
        for(auto v:adj[u])if(v!=p){
            int csz=dfs(v,u);
            if(csz>mx)hv[u]=v,mx=csz;
            sz+=csz;
        }
        return sz;
    }
    void build(vector<vector<int>>_adj,int _n){
        n=_n;
        id=_n-1;
        adj=_adj;
        for(int i=0;i<=4*n;i++)hv[i]=type[i]=l[i]=r[i]=p[i]=-1;
        dfs(0,-1);
        rt=compress(0).first;
    }
    int add(int i,int lch,int rch,int t){
        if(i==-1)i=++id;
        p[i]=-1,type[i]=t;
        if(lch!=-1)l[i]=lch,p[lch]=i;
        if(rch!=-1)r[i]=rch,p[rch]=i;
        return i;
    }
    pair<int,int>merge(vector<pair<int,int>>v,int t){
        if(v.size()==1)return v[0];
        int sz=0;
        vector<pair<int,int>>l,r;
        for(auto x:v)sz+=x.second;
        for(auto x:v){
            if(sz>x.second)l.push_back(x);
            else r.push_back(x);
            sz-=2*x.second;
        }
        auto lch=merge(l,t);
        auto rch=merge(r,t);
        return {add(-1,lch.first,rch.first,t),lch.second+rch.second};
    }
    pair<int,int>compress(int i){
        vector<pair<int,int>>v;
        for(;i!=-1;i=hv[i])v.push_back(add_vertex(i));
        return merge(v,1);
    }
    pair<int,int>add_vertex(int i){
        auto x=rake(i);
        return {add(i,x.first,-1,(x.first==-1?3:2)),x.second+1};
    }
    pair<int,int>rake(int i){
        vector<pair<int,int>>v;
        for(auto x:adj[i])if(x!=hv[i])v.push_back(add_edge(x));
        return v.empty()?make_pair(-1,0):merge(v,4);
    }
    pair<int,int>add_edge(int i){
        auto x=compress(i);
        return {add(-1,x.first,-1,5),x.second};
    }
    void print(){
        for(int i=0;i<=id;i++){
            cerr<<i<<":"<<datas[i].t1<<" "<<datas[i].t3<<" "<<datas[i].s1<<" "<<datas[i].s3<<" "<<datas[i].ans<<"\n";
        }
    }
}tr;
vector<vector<int>>adj;
int n;
int ar[200005];
info compress(info l,info r){
    return l+r;
}
info add_vertex(info u,int i){
    if(ar[i]==1){
        u.t1++;
        return u;
    }else if(ar[i]==3){
        u.t3++;
        return u;
    }else{
        u.s1+=u.t1;
        u.s3+=u.t3;
        u.chsz++;
        return u;
    }
}
info vertex(int i){
    info u;
    if(ar[i]==1)u.t1++;
    if(ar[i]==3)u.t3++;
    if(ar[i]==2)u.chsz++;
    return u;
}
info rake(info a,info b){
    return a+b;
}
info add_edge(info a){
    a.chsz=0;
    return a;
}
void upd(int i,int t){
    if(t==1){
        datas[i]=compress(datas[tr.l[i]],datas[tr.r[i]]);
    }else if(t==2){
        datas[i]=add_vertex(datas[tr.l[i]],i);
    }else if(t==3){
        datas[i]=vertex(i);
    }else if(t==4){
        datas[i]=rake(datas[tr.l[i]],datas[tr.r[i]]);
    }else{
        datas[i]=add_edge(datas[tr.l[i]]);
    }
}
void dfs(int u,int p){
    //cerr<<u<<"\n";
    if(tr.l[u]!=-1)dfs(tr.l[u],u);
    if(tr.r[u]!=-1)dfs(tr.r[u],u);
    upd(u,tr.type[u]);
}
void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
    //cerr<<"work\n";
    adj.resize(n=N);
    for(int i=0;i<n;i++)ar[i]=F[i]+1;
    //for(int i=0;i<n;i++)cerr<<ar[i]<<"\n";
    for(int i=0;i<n-1;i++)adj[U[i]].push_back(V[i]);
    tr.build(adj,n);
    //cerr<<"work\n";
    dfs(tr.rt,-1);
    //tr.print();
    //cerr<<"\n";
    //cerr<<"work\n";
}

void change(int X, int Y) {
    ar[X]=++Y;
    for(;X!=-1;X=tr.p[X])upd(X,tr.type[X]);
    //cerr<<"upd:"<<X<<" "<<Y<<"\n";
    //tr.print();
}
long long num_tours() {
    //tr.print();
    return datas[tr.rt].ans;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 34
• Subtask 7: 0 / 14