oj.uz

Submission #884135

# Submission time Handle Problem Language Result Execution time Memory
884135 2023-12-06T16:04:40 Z vjudge1 Cats or Dogs (JOI18_catdog) C++17
0 / 100
 3 ms 15192 KB 
#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]);
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 15192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 15192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 15192 KB Output isn't correct
2 Halted 0 ms 0 KB -