제출 #884135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884135		vjudge1	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	3 ms	15192 KiB

catdog

#include <bits/stdc++.h>

using namespace std;

vector<int> adj[500005];
int stare[500005];
long long dp[500005][3];
const long long INF = 1e9;

int lim;

void reset()
{
    for(int i = 1; i <= lim; i++)
    {
        dp[i][0] = INF;
        dp[i][1] = INF;
        dp[i][2] = INF;
    }

    return;
}

void calcdp(int nod, int parent)
{
    for(auto it : adj[nod])
    {
        if(it != parent)
        {
            calcdp(it, nod);
        }
    }

    if(adj[nod].size() == 1)
    {
        dp[nod][0] = INF;
        dp[nod][1] = INF;
        dp[nod][2] = 0;
        return;
    }

    if(stare[nod] == 1)
    {
        dp[nod][0] = INF;
        dp[nod][1] = 0;
        dp[nod][2] = INF;
        for(auto it : adj[nod])
        {
            if(it != parent)
            {
                dp[nod][1] += min(dp[it][0] + 1, min(dp[it][1], dp[it][2]));
            }
        }
    }
    else if(stare[nod] == 2)
    {
        dp[nod][0] = 0;
        dp[nod][1] = INF;
        dp[nod][2] = INF;
        for(auto it : adj[nod])
        {
            if(it != parent)
            {
                dp[nod][0] += min(dp[it][0], min(dp[it][1] + 1, dp[it][2]));
            }
        }
    }
    else
    {
        dp[nod][0] = 0;
        dp[nod][1] = 0;
        dp[nod][2] = 0;
        for(auto it : adj[nod])
        {
            if(it != parent)
            {
                dp[nod][0] += min(dp[it][0], min(dp[it][1] + 1, dp[it][2]));
                dp[nod][1] += min(dp[it][0] + 1, min(dp[it][1], dp[it][2]));
                dp[nod][2] = max(dp[nod][2], dp[it][2]);
            }
        }
    }
}

void initialize(int n, vector<int> a, vector<int> b)
{
    lim = n;
    for(int i = 0; i < a.size(); i++)
    {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
}

int cat(int v)
{
    stare[v] = 1;
    reset();
    calcdp(1, 1);
    return min(min(dp[1][0], dp[1][1]), dp[1][2]);
}

int dog(int v)
{
    stare[v] = 2;
    reset();
    calcdp(1, 1);
    return min(min(dp[1][0], dp[1][1]), dp[1][2]);
}

int neighbor(int v)
{
    stare[v] = 0;
    reset();
    calcdp(1, 1);
    return min(min(dp[1][0], dp[1][1]), dp[1][2]);
}

컴파일 시 표준 에러 (stderr) 메시지

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~

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