oj.uz

답안 #794596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794596 2023-07-26T16:05:37 Z normankr07 Cats or Dogs (JOI18_catdog) C++17
38 / 100
 3000 ms 28620 KB 
/*
Templete by norman/KNN-07
Who tf even love CP :sob:
*/

#ifndef LOCAL
#pragma GCC optimize("Ofast,unroll-loops,inline")
// Bitwise pragma fuck
// #pragma GCC target("avx,avx2,bmi")

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("arch=skylake")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#endif

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

// Wish you can debug? YesYes
#ifndef LOCAL
#define cerr \
    if (0)   \
    cerr
#endif

// Policy based DS?
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// Who tf deal with overflow
// #define int long long

/*
pbds blog :
https://codeforces.com/blog/entry/11080
https://codeforces.com/blog/entry/13279
*/
// Useful pbds
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template <typename T>
// using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

#define el '\n'
#define mpp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define emp emplace_back
#define fi first
#define nd second
#define forinc(i, a, b) for (int i = (a); i <= (b); i++)
#define fordec(i, a, b) for (int i = (a); i >= (b); i--)
#define alle(x) (x).begin(), (x).end()
#define ralle(x) (x).rbegin(), (x).rend()
#define mms(a, v) memset(a, v, sizeof(a))
#define lwb(a, v) lower_bound((a).begin(), (a).end(), v)
#define upb(a, v) upper_bound((a).begin(), (a).end(), v)
#define bit(i, a) (((a) >> (i)) & 1)

#define BIT_SET(a, b) ((a) |= (1ULL << (b)))
#define BIT_CLEAR(a, b) ((a) &= ~(1ULL << (b)))
#define BIT_FLIP(a, b) ((a) ^= (1ULL << (b)))
#define BIT_CHECK(a, b) (!!((a) & (1ULL << (b))))
#define BITMASK_SET(x, mask) ((x) |= (mask))
#define BITMASK_CLEAR(x, mask) ((x) &= (~(mask)))
#define BITMASK_FLIP(x, mask) ((x) ^= (mask))
#define BITMASK_CHECK_ALL(x, mask) (!(~(x) & (mask)))
#define BITMASK_CHECK_ANY(x, mask) ((x) & (mask))
#define POPCNT(mask) __builtin_popcount(mask)
#define POPCNTLL(mask) __builtin_popcountll(mask)
#define CTZ(mask) __builtin_ctz(mask)
#define CTZLL(mask) __builtin_ctzll(mask)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef vector<bool> vb;

template <typename T, typename U>
inline void maximize(T &x, U y)
{
    if (y < x)
        x = y;
}
template <typename T, typename U>
inline void minimize(T &x, U y)
{
    if (x < y)
        x = y;
}
inline int add_m(int a, int b, int mod)
{
    int res = a + b;
    return (res >= mod ? res - mod : res);
}
inline int mod_neg(int a, int b, int mod)
{
    int res;
    if (abs(a - b) < mod)
        res = a - b;
    else
        res = (a - b) % mod;
    return (res < 0 ? res + mod : res);
}
inline int mul_wmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return (res >= c ? res % c : res);
}
inline int mul_wnmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return ((res % c) + c) % c;
}

// Debugger Utils
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

template <size_t i, class T>
ostream &print_tuple_utils(ostream &out, const T &tup)
{
    if constexpr (i == tuple_size<T>::value)
        return out << ")";
    else
        return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template <class... U>
ostream &operator<<(ostream &out, const tuple<U...> &t)
{
    return print_tuple_utils<0, tuple<U...>>(out, t);
}
#define db(val) "[" #val " = " << (val) << "] "
// End if debugger utils

namespace Hasher
{
    struct custom_hash
    {
        static uint32_t splitmix64(uint32_t x)
        {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }
        size_t operator()(uint64_t x) const
        {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    struct hash_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = custom_hash{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
    struct hash_pair_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = hash_pair{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
}
using namespace Hasher;

const string taskname = "";
const bool tc = false;

const int oo = 1e9, mod = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll ool = 1e18;
const ldb eps = 1e-6;
const int MAXN = 1e6;

/*
Author: normankr07
Problem: JOI18_catdog

Submission links:
    oj.uz
Editorial links:
    https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2018/2018-open-catdog-sol-en.pdf
Algorithm:
    Let us restate the problem in terms of graphs. Then the garden becomes a tree structure, and each hut becomes
a vertex. For simplicity, a hut with a cat is called a “red” vertex, and a hut with a dog is called a “blue” vertex
subtask 2 : DP
*/

vi adj[MAXN];
ll R[MAXN], B[MAXN];
char color[MAXN];
bool vis[MAXN];
int n;

// initialize function (init your mom)
void initialize(int N, vi a, vi b)
{
    n = N;
    for (int i = 0; i < n - 1; i++)
    {
        adj[a[i]].pb(b[i]);
        adj[b[i]].pb(a[i]);
    }
}

// DFS DP
void DFS(int u, int par)
{
    B[u] = R[u] = 0;
    for (auto v : adj[u])
    {
        if (v != par)
        {
            DFS(v, u);
            B[u] += min(B[v], R[v] + 1);
            R[u] += min(R[v], B[v] + 1);
        }
    }
    if (color[u] == 'R')
        R[u] = oo;
    if (color[u] == 'B')
        B[u] = oo;
}

int cat(int v)
{
    color[v] = 'R';
    DFS(1, 0);
    return min(R[1], B[1]);
}

int dog(int v)
{
    color[v] = 'B';
    DFS(1, 0);
    return min(R[1], B[1]);
}

int neighbor(int v)
{
    color[v] = 'N';
    DFS(1, 0);
    return min(R[1], B[1]);
}

#ifdef LOCAL
void solve()
{
    int N;
    cin >> N;
    vi A(N - 1), B(N - 1);
    for (int i = 0; i < N - 1; i++)
        cin >> A[i] >> B[i];
    initialize(N, A, B);
    int Q;
    cin >> Q;
    int t, v;
    while (Q--)
    {
        cin >> t >> v;
        if (t == 1)
            cout << cat(v) << el;
        else if (t == 2)
            cout << dog(v) << el;
        else
            cout << neighbor(v);
    }
}

int32_t main()
{
    if (fopen((taskname + ".inp").c_str(), "r"))
    {
        freopen((taskname + ".inp").c_str(), "r", stdin);
        freopen((taskname + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tsc = 1;
    if (tc)
    {
        cin >> tsc;
    }
    while (tsc--)
    {
        solve();
        cout << el;
    }

    cerr << "\n"
         << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
#endif

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 14 ms 23788 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 15 ms 23784 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23760 KB Output is correct
7 Correct 14 ms 23776 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 15 ms 23712 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 14 ms 23796 KB Output is correct
12 Correct 14 ms 23764 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 14 ms 23732 KB Output is correct
15 Correct 14 ms 23764 KB Output is correct
16 Correct 14 ms 23692 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 14 ms 23788 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 15 ms 23784 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23760 KB Output is correct
7 Correct 14 ms 23776 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 15 ms 23712 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 14 ms 23796 KB Output is correct
12 Correct 14 ms 23764 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 14 ms 23732 KB Output is correct
15 Correct 14 ms 23764 KB Output is correct
16 Correct 14 ms 23692 KB Output is correct
17 Correct 19 ms 23800 KB Output is correct
18 Correct 20 ms 23764 KB Output is correct
19 Correct 19 ms 23876 KB Output is correct
20 Correct 14 ms 23812 KB Output is correct
21 Correct 15 ms 23792 KB Output is correct
22 Correct 15 ms 23764 KB Output is correct
23 Correct 22 ms 23888 KB Output is correct
24 Correct 20 ms 23844 KB Output is correct
25 Correct 17 ms 23764 KB Output is correct
26 Correct 15 ms 23764 KB Output is correct
27 Correct 15 ms 23764 KB Output is correct
28 Correct 16 ms 23892 KB Output is correct
29 Correct 24 ms 23944 KB Output is correct
30 Correct 15 ms 23816 KB Output is correct
31 Correct 15 ms 23796 KB Output is correct
32 Correct 16 ms 23788 KB Output is correct

Subtask #3
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 14 ms 23788 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 15 ms 23784 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23760 KB Output is correct
7 Correct 14 ms 23776 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 15 ms 23712 KB Output is correct
10 Correct 14 ms 23764 KB Output is correct
11 Correct 14 ms 23796 KB Output is correct
12 Correct 14 ms 23764 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 14 ms 23732 KB Output is correct
15 Correct 14 ms 23764 KB Output is correct
16 Correct 14 ms 23692 KB Output is correct
17 Correct 19 ms 23800 KB Output is correct
18 Correct 20 ms 23764 KB Output is correct
19 Correct 19 ms 23876 KB Output is correct
20 Correct 14 ms 23812 KB Output is correct
21 Correct 15 ms 23792 KB Output is correct
22 Correct 15 ms 23764 KB Output is correct
23 Correct 22 ms 23888 KB Output is correct
24 Correct 20 ms 23844 KB Output is correct
25 Correct 17 ms 23764 KB Output is correct
26 Correct 15 ms 23764 KB Output is correct
27 Correct 15 ms 23764 KB Output is correct
28 Correct 16 ms 23892 KB Output is correct
29 Correct 24 ms 23944 KB Output is correct
30 Correct 15 ms 23816 KB Output is correct
31 Correct 15 ms 23796 KB Output is correct
32 Correct 16 ms 23788 KB Output is correct
33 Execution timed out 3053 ms 28620 KB Time limit exceeded
34 Halted 0 ms 0 KB -