Submission #993625

#TimeUsernameProblemLanguageResultExecution timeMemory
993625danikoynovWells (CEOI21_wells)C++14
0 / 100
1 ms704 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 1e4 + 10; int n, k; vector < int > adj[maxn]; void input() { cin >> n >> k; for (int i = 1; i < n; i ++) { int v, u; cin >> v >> u; adj[v].push_back(u); adj[u].push_back(v); } } int used[maxn]; void bfs(int s) { for (int i = 1; i <= n; i ++) used[i] = 0; queue < int > q; q.push(s); used[s] = 1; while(!q.empty()) { int v = q.front(); q.pop(); for (int u : adj[v]) { if (used[u] == 0) { used[u] = used[v] + 1; q.push(u); } } } } int tin[maxn], ord[2 * maxn], timer; int depth[maxn]; void dfs(int v, int p) { ord[ ++ timer] = v; tin[v] = timer; for (int u : adj[v]) { if (u == p) continue; depth[u] = depth[v] + 1; dfs(u, v); ord[++ timer] = v; } } const int maxlog = 23; int dp[maxlog][2 * maxn], lg[2 * maxn]; void build_sparse_table() { for (int i = 1; i <= timer; i ++) { lg[i] = lg[i / 2] + 1; dp[0][i] = ord[i]; } for (int j = 1; j < lg[timer]; j ++) { for (int i = 1; i <= timer - (1 << j) + 1; i ++) { dp[j][i] = dp[j - 1][i + (1 << (j - 1))]; if (depth[dp[j - 1][i]] < depth[dp[j][i]]) dp[j][i] = dp[j - 1][i]; } } /** for (int j = 0; j < lg[timer]; j ++, cout << endl) for (int i = 1; i <= timer - (1 << j) + 1; i ++) cout << dp[j][i] << " ";*/ } int lca(int v, int u) { int l = tin[v], r = tin[u]; if (l > r) swap(l, r); int len = lg[r - l + 1] - 1; assert((1 << len) <= (r - l + 1)); int lca = dp[len][r - (1 << len) + 1]; if (depth[dp[len][l]] < depth[lca]) lca = dp[len][l]; return lca; } int dist(int v, int u) { return depth[v] + depth[u] - 2 * depth[lca(v, u)]; } vector < int > st; void check() { for (int s = 4; s <= 4; s ++) { bfs(s); for (int i = 1; i <= n; i ++) { if (used[i] % k == 1) st.push_back(i); } bool done = true; for (int v : st) { if (!done) break; for (int u : st) { if (dist(v, u) % k != 0) { ///cout << "dist " << lca(v, u) << " " << v << " " << u << endl; done = false; break; } } } if (done) { cout << "YES" << endl; cout << 0 << endl; return; } } cout << "NO" << endl; cout << 0 << endl; } void solve() { input(); dfs(1, -1); build_sparse_table(); ///cout << dist(2, 6) << endl; check(); } int main() { speed(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...