Submission #994166

#	Time	Username	Problem	Language	Result	Execution time	Memory
994166		bachhoangxuan	JOI tour (JOI24_joitour)	C++17	100 / 100	1707 ms	102156 KiB

joitour

#include "joitour.h"
#include<bits/stdc++.h>
using namespace std;
using i32 = int;
#define int long long
const int maxn = 2e5+5;
int N,C[maxn];
vector<int> edge[maxn];

int L[maxn],R[maxn],T,ans,P[maxn];
int child[maxn],son[maxn],head[maxn],lst[maxn],par[maxn];

void pre_dfs(int u,int p){
    child[u]=1;par[u]=p;
    for(int v:edge[u]){
        if(v==p) continue;
        pre_dfs(v,u);
        child[u]+=child[v];
        if(child[v]>child[son[u]]) son[u]=v;
    }
}
void hld_dfs(int u,int p,int t){
    L[u]=++T;P[T]=u;
    if(t) head[u]=head[p];
    else head[u]=u;
    //cout << "head " << u << ' ' << head[u] << ' ' << head[p] << '\n';
    lst[head[u]]=u;
    if(son[u]) hld_dfs(son[u],u,1);
    for(int v:edge[u]) if(v!=p && v!=son[u]) hld_dfs(v,u,0);
    R[u]=T;
}

struct Node{
    int s0=0,s2=0,c0=0,c2=0;
    int sum=0,total=0;
    Node(int s0=0,int s2=0,int c0=0,int c2=0):s0(s0),s2(s2),c0(c0),c2(c2){
        sum=c0*c2;
    }
    friend Node operator+(Node a,Node b){
        Node res;
        res.s0=a.s0+b.s0;
        res.s2=a.s2+b.s2;
        res.c0=a.c0+b.c0;
        res.c2=a.c2+b.c2;
        res.sum=a.sum+b.sum;
        res.total=a.total+b.total+a.c0*b.s2+a.c2*b.s0+a.s0*b.c2+a.s2*b.c0;
        return res;
    };
    friend Node operator-(Node a,Node b){
        Node res;
        res.s0=a.s0-b.s0;
        res.s2=a.s2-b.s2;
        res.c0=a.c0-b.c0;
        res.c2=a.c2-b.c2;
        res.sum=a.sum-b.sum;
        res.total=a.total-b.total-(res.c0*b.s2+res.c2*b.s0+res.s0*b.c2+res.s2*b.c0);
        return res;
    };
}cc[maxn];
struct node{
    int total=0;
    int c0=0,c1=0,c2=0;
    int l0=0,l2=0,r0=0,r2=0;
    node(){}
    friend node operator+(node a,node b){
        node res;
        res.c0=a.c0+b.c0;
        res.c1=a.c1+b.c1;
        res.c2=a.c2+b.c2;
        res.l0=a.l0+b.l0+a.c0*b.c1;
        res.l2=a.l2+b.l2+a.c2*b.c1;
        res.r0=a.r0+b.r0+a.c1*b.c0;
        res.r2=a.r2+b.r2+a.c1*b.c2;
        res.total=a.total+b.total+a.l0*b.c2+a.l2*b.c0+a.c0*b.r2+a.c2*b.r0;
        return res;
    }
}tree[4*maxn];
node query(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return node();
    if(tl<=l && r<=tr) return tree[id];
    int mid=(l+r)>>1;
    return query(l,mid,id<<1,tl,tr)+query(mid+1,r,id<<1|1,tl,tr);
}
void update(int l,int r,int id,int p,node val){
    if(l==r){
        tree[id]=val;
        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);
    tree[id]=tree[id<<1]+tree[id<<1|1];
}

void change(i32 u, i32 d) {
    //cout << "change " << u << ' ' << d << '\n';
    u++;C[u]=d;
    while(u){
        int v=head[u],w=lst[v],p=par[v];
        //cout << u << ' ' << v << ' ' << w << '\n';
        node cur=query(1,N,1,L[v],L[w]);
        ans-=cur.total;
        if(p) cc[p]=cc[p]-Node(cur.r0,cur.r2,cur.c0,cur.c2);
        node val;
        val.total=cc[u].total;
        val.l0=val.r0=cc[u].s0;
        val.l2=val.r2=cc[u].s2;
        val.c0=cc[u].c0;
        val.c2=cc[u].c2;
        node add;
        if(C[u]==0) add.c0++;
        else if(C[u]==2) add.c2++;
        else{
            add.c1++;
            add.total+=cc[u].c0*cc[u].c2-cc[u].sum;
        }
        val=val+add;
        //cout << val.c0 << ' ' << val.c1 << ' ' << val.c2 << ' ' << val.l0 <<  ' ' << val.l2 << ' ' << val.r0 << ' ' << val.r2 << ' ' << val.total << '\n';
        val.l0=val.r0=max(val.l0,val.r0);
        val.l2=val.r2=max(val.l2,val.r2);
        update(1,N,1,L[u],val);
        cur=query(1,N,1,L[v],L[w]);
        ans+=cur.total;
        if(p) cc[p]=cc[p]+Node(cur.r0,cur.r2,cur.c0,cur.c2);
        u=p;
    }
}

void init(i32 _N, std::vector<i32> F, std::vector<i32> U, std::vector<i32> V,
          i32 Q) {
    N=_N;
    for(int i=0;i<N-1;i++){
        U[i]++;V[i]++;
        edge[U[i]].push_back(V[i]);
        edge[V[i]].push_back(U[i]);
    }
    pre_dfs(1,0);
    hld_dfs(1,0,0);
    for(int i=1;i<=N;i++){
        int u=P[i];
        change(u-1,F[u-1]);
    }
}



long long num_tours() {
    return ans;
}

#undef int

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