Submission #125490

#	Time	Username	Problem	Language	Result	Execution time	Memory
125490		arnold518	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3023 ms	8100 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];

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]);
    }
}

void dfs(int now, int par)
{
    int i, j;

    for(int nxt : adj[now])
    {
        if(nxt==par) continue;
        dfs(nxt, now);

        dp[now][1]+=min(dp[nxt][1], dp[nxt][2]+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;
}

int solve()
{
    memset(dp, 0, sizeof(dp));
    dfs(1, -1);
    return min(dp[1][2], dp[1][1]);
}

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

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

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

Compilation message (stderr)

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

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