oj.uz

Submission #302584

# Submission time Handle Problem Language Result Execution time Memory
302584 2020-09-18T20:24:50 Z gevacrt Cats or Dogs (JOI18_catdog) C++17
0 / 100
 1 ms 256 KB 
#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()


int N; vi col;
vvi adj, dp;

void dfs(int u, int p){
    dp[u][0] = dp[u][1] = dp[u][2] = 0;
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
        dp[u][0] += min({dp[v][0], dp[v][1]+1, dp[v][2]+1});
        dp[u][1] += min({dp[v][0], dp[v][1], dp[v][2]+1});
        dp[u][2] += min({dp[v][0], dp[v][1]+1, dp[v][2]});
    }
    if(col[u] == 1) dp[u][0]++, dp[u][2]++;
    else if(col[u] == 2) dp[u][0]++, dp[u][1]++;
    return; 
}

int calc(){
    dfs(0, 0);
    return *min_element(all(dp[0]));
}

void initialize(int n, vi a, vi b){
    N = n; adj = vvi(n); col = vi(n);
    dp = vvi(n, vi(3));

    for(int x = 0; x < n-1; x++){
        adj[a[x]-1].push_back(b[x]-1);
        adj[b[x]-1].push_back(a[x]-1);
    }
    return;
}

// cat ==> 1
int cat(int v){
    v--; col[v] = 1;
    return calc();
}

// dog ==> 2
int dog(int v){
    v--; col[v] = 2;
    return calc();
}

// neighbor ==> 0
int neighbor(int v){
    v--; col[v] = 0;
    return calc();
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 62.0

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