| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833963 |
2023-08-22T09:49:17 Z |
vjudge1 |
Pastiri (COI20_pastiri) |
C++17 |
|
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
