oj.uz

답안 #833963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833963 2023-08-22T09:49:17 Z vjudge1 Pastiri (COI20_pastiri) C++17
100 / 100
 418 ms 86708 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

#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 = "WHARF";
const bool tc = 0;

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:
Submission links:
Editorial links:
Algorithm:
*/
int n, k;
vector<int> adj[MAXN];
bool vis[MAXN];
int dp[MAXN], d[MAXN];
vector<int> ans;

void dfs(int x, int par)
{
    dp[x] = -1;
    if (!d[x])
        vis[x] = 1;
    for (int k : adj[x])
    {
        if (k == par)
            continue;
        dfs(k, x);
        if (vis[k])
            vis[x] = 1;
        dp[x] = max(dp[x], dp[k] - 1);
    }
    if (vis[x] && dp[x] == d[x])
        vis[x] = 0;
    if (vis[x] && d[par] != d[x] + 1)
    {
        ans.push_back(x);
        dp[x] = d[x];
        vis[x] = 0;
    }
}

void solve()
{
    cin >> n >> k;
    int u, v;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    for (int i = 1; i <= n; i++)
        d[i] = -1;

    queue<int> q;
    while (k--)
    {
        int memay;
        cin >> memay;
        d[memay] = 0;
        q.push(memay);
    }

    while (q.size())
    {
        auto front = q.front();
        for (int k : adj[front])
        {
            if (d[k] == -1)
            {
                d[k] = d[front] + 1;
                q.push(k);
            }
        }
        q.pop();
    }

    dfs(1, 0);

    cout << ans.size() << el;
    for (auto x : ans)
        cout << x << ' ';
}

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;
    }
#ifdef LOCAL
    cerr << "\n"
         << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Compilation message

pastiri.cpp: In function 'int32_t main()':
pastiri.cpp:290:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  290 |         freopen((taskname + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:291:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  291 |         freopen((taskname + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 82508 KB Output is correct
2 Correct 157 ms 83008 KB Output is correct
3 Correct 159 ms 83012 KB Output is correct
4 Correct 218 ms 86708 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 14 ms 24024 KB Output is correct
3 Correct 316 ms 44224 KB Output is correct
4 Correct 300 ms 46540 KB Output is correct
5 Correct 402 ms 43972 KB Output is correct
6 Correct 418 ms 47396 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 13 ms 23912 KB Output is correct
3 Correct 12 ms 23920 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 13 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23828 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 13 ms 23868 KB Output is correct
12 Correct 17 ms 23896 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23888 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 44916 KB Output is correct
2 Correct 347 ms 44708 KB Output is correct
3 Correct 354 ms 46112 KB Output is correct
4 Correct 370 ms 43856 KB Output is correct
5 Correct 251 ms 42212 KB Output is correct
6 Correct 332 ms 50456 KB Output is correct
7 Correct 373 ms 48952 KB Output is correct
8 Correct 368 ms 48740 KB Output is correct
9 Correct 409 ms 44112 KB Output is correct
10 Correct 382 ms 43888 KB Output is correct
11 Correct 278 ms 45816 KB Output is correct
12 Correct 249 ms 47628 KB Output is correct
13 Correct 279 ms 48452 KB Output is correct
14 Correct 226 ms 47384 KB Output is correct
15 Correct 38 ms 27244 KB Output is correct
16 Correct 336 ms 42424 KB Output is correct
17 Correct 238 ms 49216 KB Output is correct
18 Correct 307 ms 45760 KB Output is correct
19 Correct 380 ms 57148 KB Output is correct
20 Correct 413 ms 61960 KB Output is correct
21 Correct 367 ms 50736 KB Output is correct
22 Correct 362 ms 51380 KB Output is correct