제출 #1235744

#제출 시각아이디문제언어결과실행 시간메모리
1235744gs13105The Ties That Guide Us (CEOI23_incursion)C++20
100 / 100
152 ms7456 KiB
#include <bits/stdc++.h> using namespace std; #include "incursion.h" int n; vector<int> adj[45010]; vector<int> cen; int siz[45010]; int par[45010]; void f(int x, int p) { bool ok = 1; siz[x] = 1; for(int y : adj[x]) { if(y == p) continue; f(y, x); siz[x] += siz[y]; if(siz[y] > n / 2) ok = 0; } if(n - siz[x] > n / 2) ok = 0; if(ok) cen.push_back(x); } void g(int x, int p) { par[x] = p; siz[x] = 1; for(int y : adj[x]) { if(y == p) continue; g(y, x); siz[x] += siz[y]; } } void init(vector<pair<int, int>> &F) { n = (int)F.size() + 1; for(auto [x, y] : F) { adj[x].push_back(y); adj[y].push_back(x); } f(1, -1); if((int)cen.size() == 1) cen.push_back(-1); assert((int)cen.size() == 2); g(cen[0], cen[1]); if(cen[1] != -1) g(cen[1], cen[0]); } vector<int> mark(vector<pair<int, int>> F, int safe) { init(F); vector<int> res(n); int x = safe; while(1) { res[x - 1] = 1; if(x == cen[0] || x == cen[1]) break; x = par[x]; } return res; } void locate(vector<pair<int, int>> F, int curr, int t) { init(F); int x = curr; while(t == 0) { t = visit(par[x]); x = par[x]; } while(1) { vector<pair<int, int>> nx; for(int y : adj[x]) { if(y == par[x]) continue; nx.push_back({ siz[y], y }); } sort(nx.rbegin(), nx.rend()); bool ok = 1; for(auto [_, y] : nx) { if(visit(y)) { ok = 0; x = y; break; } visit(x); } if(ok) return; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...