Submission #998015

#	Time	Username	Problem	Language	Result	Execution time	Memory
998015		imarn	JOI tour (JOI24_joitour)	C++17	0 / 100	2652 ms	463864 KiB

joitour

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int mxn=2e5+5;
vi f,g[mxn];int n;ll ans=0;
int tin[mxn][18],tout[mxn][18],cnt[18]{0},ids[mxn][18]{0};
int lv[mxn]{0},pr[mxn]{0};
struct lazy{
    int t[4*mxn]{0},lz[4*mxn]{0};
    void push(int i,int l,int r){
        t[i]+=lz[i];
        if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int i,int l,int r,int tl,int tr,int a){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]+=a;push(i,l,r);return;
        }int m=(l+r)>>1;update(2*i,l,m,tl,tr,a);update(2*i+1,m+1,r,tl,tr,a);
    }
    int qr(int i,int l,int r,int idx){
        push(i,l,r);
        if(r<idx||l>idx)return 0;
        if(l==r)return t[i];
        int m=(l+r)>>1;
        return max(qr(2*i,l,m,idx),qr(2*i+1,m+1,r,idx));
    }
}t1[3][18];
struct seg{
    int t[4*mxn]{0};
    void update(int i,int l,int r,int idx,int v){
        if(r<idx||l>idx)return;
        if(l==r)return void(t[i]+=v);
        int m=(l+r)>>1;update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
        t[i]=t[2*i]+t[2*i+1];
    }
    int qr(int i,int l,int r,int tl,int tr){
        if(r<tl||l>tr)return 0;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
    }
}t2[3][18];
int sz[mxn];
bool vis[mxn]{0};
int getsz(int u,int p){
    sz[u]=1;
    for(auto v:g[u]){
        if(v==p||vis[v])continue;
        sz[u]+=getsz(v,u);
    }return sz[u];
}
int getct(int u,int p,int rs){
    for(auto v:g[u]){
        if(v==p||vis[v])continue;
        if(sz[v]*2>rs)return getct(v,u,rs);
    }return u;
}
vl dp[7][mxn];
ll tdp[7][mxn]{0};
// dp[0]->0,dp[1]->1,dp[2]->2,dp[3]->0,1,dp[4]->1,2,dp[5]->2,1,dp[6]->1,0
void get01234(int u,int p,int x,int id){
    dp[f[u]][x][id]++;ids[u][lv[x]]=id;
    if(f[u]==1)dp[3][x][id]+=dp[0][x][id];
    if(f[u]==2)dp[4][x][id]+=dp[1][x][id];
    tin[u][lv[x]]=++cnt[lv[x]];
    for(int i=0;i<3;i++)t1[i][lv[x]].update(1,1,n,tin[u][lv[x]],tin[u][lv[x]],dp[i][x][id]);
    for(auto v:g[u]){
        if(vis[v]||v==p)continue;
        get01234(v,u,x,id);
    }tout[u][lv[x]]=cnt[lv[x]];
}
void get56(int u,int p,int x,int id){
    for(auto v:g[u]){
        if(vis[v]||v==p)continue;
        get56(v,u,x,id);
    }t2[f[u]][lv[x]].update(1,1,n,tin[u][lv[x]],1);
    if(f[u]==2)dp[5][x][id]+=t2[1][lv[x]].qr(1,1,n,tin[u][lv[x]],tout[u][lv[x]]);
    if(f[u]==1)dp[6][x][id]+=t2[0][lv[x]].qr(1,1,n,tin[u][lv[x]],tout[u][lv[x]]);
}
void play(int u,int p,int l){
    int x=getct(u,u,getsz(u,u));vis[x]=1;int id=0;
    lv[x]=l;pr[u]=p;tin[x][lv[x]]=++cnt[lv[x]];
    for(auto v:g[x]){
        if(vis[v])continue;
        for(int i=0;i<7;i++)dp[i][x].pb(0);
        get01234(v,u,x,id);get56(v,u,x,id);
        for(int i=0;i<7;i++)tdp[i][x]+=dp[i][x][id];id++;
    }tout[x][lv[x]]=cnt[lv[x]];
    for(auto v:g[x]){
        if(vis[v])continue;
        ans+=dp[0][x][ids[v][lv[x]]]*(tdp[4][x]-dp[4][x][ids[v][lv[x]]]);
        ans+=dp[6][x][ids[v][lv[x]]]*(tdp[2][x]-dp[2][x][ids[v][lv[x]]]);
        if(f[x]==1){
            ans+=dp[0][x][ids[v][lv[x]]]*(tdp[2][x]-dp[2][x][ids[v][lv[x]]]);
        }
    }
    if(f[x]==2)ans+=tdp[6][x];
    if(f[x]==0)ans+=tdp[4][x];
    for(auto v:g[x]){
        if(vis[v])continue;
        play(v,x,l+1);
    }
}
void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V,int Q){
    f=F,n=N;for(int i=0;i<N-1;i++)g[U[i]].pb(V[i]),g[V[i]].pb(U[i]);
    play(0,-1,0);
}

void change(int X, int Y){
}

long long num_tours() {
  return ans;
}

Compilation message (stderr)

joitour.cpp: In function 'void play(int, int, int)':
joitour.cpp:100:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  100 |         for(int i=0;i<7;i++)tdp[i][x]+=dp[i][x][id];id++;
      |         ^~~
joitour.cpp:100:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  100 |         for(int i=0;i<7;i++)tdp[i][x]+=dp[i][x][id];id++;
      |                                                     ^~

• 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