Submission #1141110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141110		Noproblem29	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	150 ms	32584 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const ll INF=1e17;
struct ki{
    ll dp[2][2];
    ki(int a=0,int b=0,int c=0,int d=0){
        dp[0][0]=a;
        dp[0][1]=b;
        dp[1][0]=c;
        dp[1][1]=d;
    }
};
ki operator+(const ki& x,const ki& y){
    ki res=ki(INF,INF,INF,INF);
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                for(int l=0;l<2;l++){
                    res.dp[i][l]=min(res.dp[i][l],x.dp[i][j]+(j^k)+y.dp[k][l]);
                }
            }
        }
    }
    return res;
}
struct segtree{
    
    vector<ki>t;
    int n;
    void build(int v,int tl,int tr){
        if(tl==tr){
            t[v]=ki(0,INF,INF,0);
            return;
        }
        int mid=(tl+tr)>>1ll;
        build(v*2,tl,mid);
        build(v*2+1,mid+1,tr);
        t[v]=t[v*2]+t[v*2+1];
    }
    void upd(int v,int tl,int tr,int l,int x0,int x1){
        if(tl==tr){
            t[v].dp[0][0]+=x0;
            t[v].dp[1][1]+=x1;
            return;
        }
        int mid=(tl+tr)>>1ll;
        if(l<=mid){
            upd(v*2,tl,mid,l,x0,x1);
        }
        else{
            upd(v*2+1,mid+1,tr,l,x0,x1);
        }
        t[v]=t[v*2]+t[v*2+1];
    }
    void init(int sz){
        n=sz;
        t.resize(sz*4);
        build(1,1,n);
    }
    pair<int,int> get(){
        pair<int,int>res;
        res.first=min(t[1].dp[0][0],t[1].dp[0][1]);
        res.second=min(t[1].dp[1][0],t[1].dp[1][1]);
        return {min(res.first,res.second+1),min(res.first+1,res.second)};
    }

}seg[N];
int n;
vector<int> g[N];
int c[N];
int pr[N];
int sz[N];
void dfs1(int x, int p){
    pr[x]=p;
    sz[x]=1;
    for(auto i:g[x]){
        if(i!=p){
            dfs1(i,x);
            sz[x]+=sz[i];
        }
    }
    for(auto &i:g[x]){
        if(i==p){
            swap(g[x][g[x].size()-1],i);
            g[x].pop_back();
            break;
        }
    }
    sort(g[x].begin(),g[x].end(),[](int x,int y){
        return sz[x]>sz[y];
    });
}
int tin=0;
int head[N];
int pos[N];
void dfs2(int x,int p,int cur){
    pr[x]=cur;
    if(sz[cur]==0){
        head[cur]=p;
    }
    pos[x]=++sz[cur];
    for(auto i:g[x]){
        if(g[x].front()==i){
            dfs2(i,x,cur);
        }
        else{
            dfs2(i,x,tin++);
        }
    }
}
void initialize(int _n, vector<int> a, vector<int> b){
    n = _n;
    for (int i = 0; i < n-1; i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs1(1,0);
    memset(pr,0,sizeof(pr));
    memset(sz,0,sizeof(sz));
    dfs2(1,0,tin++);
    // for(int i=1;i<=n;i++){
    //     cout<<pos[i]<<' '<<pr[i]<<' '<<sz[pr[i]]<<' '<<i<<'\n';
    // }
    for(int i=0;i<tin;i++){
        seg[i].init(sz[i]);
    }
}
int upd(int x,int x0,int x1){
    while(x!=0){
        int cur=pr[x];
        auto [a0,a1]=seg[cur].get();
        seg[cur].upd(1,1,sz[cur],pos[x],x0,x1);
        auto [b0,b1]=seg[cur].get();
        x0=b0-a0;
        x1=b1-a1;
        x=head[cur];
    }
    auto [a,b]=seg[0].get();
    return min(a,b);
}
int cat(int v){
    c[v]=1;
    int res=upd(v,N,0);
    return res;
}

int dog(int v){
    c[v]=2;
    int res=upd(v,0,N);
    return res;
}

int neighbor(int v){
    int res=0;
    if(c[v]==1){
        res=upd(v,-N,0);
    }
    else{
        res=upd(v,0,-N);
    }
    c[v]=0;
    return res;
}

Compilation message (stderr)

catdog.cpp: In function 'ki operator+(const ki&, const ki&)':
catdog.cpp:17:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   17 |     ki res=ki(INF,INF,INF,INF);
      |               ^~~
catdog.cpp:17:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   17 |     ki res=ki(INF,INF,INF,INF);
      |                   ^~~
catdog.cpp:17:23: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   17 |     ki res=ki(INF,INF,INF,INF);
      |                       ^~~
catdog.cpp:17:27: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   17 |     ki res=ki(INF,INF,INF,INF);
      |                           ^~~
catdog.cpp: In member function 'void segtree::build(int, int, int)':
catdog.cpp:35:23: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   35 |             t[v]=ki(0,INF,INF,0);
      |                       ^~~
catdog.cpp:35:27: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
   35 |             t[v]=ki(0,INF,INF,0);
      |                           ^~~

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62