Submission #124027

#	Time	Username	Problem	Language	Result	Execution time	Memory
124027		ksmzzang2003	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3039 ms	12392 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXQ = 1e5;
const int INF = 987654321;

int N, A[MAXN+10];
int dp[MAXN+10][3];
vector<int> adj[MAXN+10];
int parents[MAXN+10];
void dfs(int,int);
void initialize(int n, vector<int> A, vector<int> B)
{
    int i, j;

    N=n;
    for(i=0; i<N-1; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    dfs(1,-1);
}

void dfs(int now, int par)
{
    int i, j;
    if(parents[now]==0) parents[now] = par;
    for(int nxt : adj[now])
    {
        if(nxt==par) continue;
        dfs(nxt, now);

        if(A[now]!=2) dp[now][1]+=min(dp[nxt][1], dp[nxt][2]+1);
        if(A[now]!=1) dp[now][2]+=min(dp[nxt][1]+1, dp[nxt][2]);
    }

    if(A[now]==1) dp[now][2]=INF;
    if(A[now]==2) dp[now][1]=INF;
}

void updfs(int now)
{
    if(now==-1) return ;
    dp[now][1] = dp[now][2] =0;
    for(int nxt : adj[now])
    {
        if(nxt==parents[now]) continue;
        if(A[now]!=2) dp[now][1]+=min(dp[nxt][1], dp[nxt][2]+1);
        if(A[now]!=1) dp[now][2]+=min(dp[nxt][1]+1, dp[nxt][2]);
    }
    if(A[now]==1) dp[now][2]=INF;
    if(A[now]==2) dp[now][1]=INF;

    updfs(parents[now]);
}

int solve(int v)
{
    updfs(v);
    return min(dp[1][2], dp[1][1]);
}

int cat(int v)
{
    A[v]=1;
    return solve(v);
}

int dog(int v)
{
    A[v]=2;
    return solve(v);
}

int neighbor(int v)
{
    A[v]=0;
    return solve(v);
}

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:20:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
catdog.cpp: In function 'void dfs(int, int)':
catdog.cpp:33:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
catdog.cpp:33:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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