Submission #986149

#TimeUsernameProblemLanguageResultExecution timeMemory
986149nextgenxingDiversity (CEOI21_diversity)C++14
0 / 100
3 ms11100 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second #define all(x) begin(x), end(x) #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define F0R(i, x) FOR(i, 0, x) #define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--) #define F0Rd(i, x) FORd(i, 0, x) #define ckif(a, b, c) ((c) ? (a) : (b)) const int MAX_N = 2e5+69; const ll MOD = 1000000007; const ll INF = 1e18; int n, m; vector<int> adj[MAX_N]; int anc[MAX_N][20], dep[MAX_N], vis[MAX_N]; pii mx[MAX_N], mx2[MAX_N]; pair<int, pii> diam[MAX_N]; bool dfs(int curr, int par = -1){ vis[curr] = 1, mx[curr] = {0, curr}; for(auto x : adj[curr]){ if(x == par) continue; if(vis[x]) return false; anc[x][0] = curr; dep[x] = dep[curr]+1; if(!dfs(x, curr)) return false; if(mx[x].ff+1 >= mx[curr].ff) mx2[curr] = mx[curr], mx[curr] = mx[x], mx[curr].ff++; else if(mx[x].ff+1 >= mx2[curr].ff) mx2[curr] = mx[x], mx2[curr].ff++; if(diam[x].ff >= diam[curr].ff) diam[curr] = diam[x]; } if(mx[curr].ff+mx2[curr].ff >= diam[curr].ff) diam[curr] = {mx[curr].ff+mx2[curr].ff, {mx[curr].ss, mx2[curr].ss}}; return true; } int lca(int a, int b){ if(dep[a] > dep[b]) swap(a, b); F0Rd(i, 20) if(dep[a]+(1 << i) <= dep[b]) b = anc[b][i]; if(a == b) return a; F0Rd(i, 20) if(anc[a][i] != anc[b][i]) a = anc[a][i], b = anc[b][i]; return anc[a][0]; } int dist(int a, int b){ return dep[lca(a, b)]*2-dep[a]-dep[b]; } int main(int argc, const char * argv[]){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cin >> n >> m; F0R(i, m){ int a, b; cin >> a >> b; a--, b--; adj[a].push_back(b); adj[b].push_back(a); } if(!dfs(0)){ cout << "NO\n"; return 0; } FOR(d, 1, 20) F0R(i, n) anc[i][d] = anc[anc[i][d-1]][d-1]; int a = diam[0].ss.ff, b = diam[0].ss.ss, c = lca(a, b); F0R(i, n){ int x = c^lca(a, i)^lca(b, i); if(dist(i, x) > 2){ cout << "NO\n"; return 0; } } cout << "YES\n"; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...