Submission #890134

#TimeUsernameProblemLanguageResultExecution timeMemory
890134hafoUnique Cities (JOI19_ho_t5)C++14
64 / 100
738 ms58468 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 7; const ll oo = 1e9 + 69; int n, m, u, v, a[maxn], dep[maxn], mx_dep[maxn], res[maxn]; vector<int> g[maxn]; struct ST { struct node { int mn, cnt; friend node operator + (node a, node b) { if(mini(a.mn, b.mn)) a.cnt = b.cnt; else if(a.mn == b.mn) a.cnt += b.cnt; return a; } }; node st[4 * maxn]; int lz[4 * maxn]; void fix(int id, int l, int r) { if(!lz[id]) return; st[id].mn += lz[id]; if(l != r) { lz[id << 1] += lz[id]; lz[id << 1 | 1] += lz[id]; } lz[id] = 0; } void build(int id, int l, int r) { if(l == r) { st[id] = {0, 1}; return; } int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } void update(int id, int l, int r, int u, int v, int val) { fix(id, l, r); if(r < u || l > v) return; if(u <= l && r <= v) { lz[id] = val; fix(id, l, r); return; } int mid = l + r >> 1; update(id << 1, l, mid, u, v, val); update(id << 1 | 1, mid + 1, r, u, v, val); st[id] = st[id << 1] + st[id << 1 | 1]; } node get(int id, int l, int r, int u, int v) { fix(id, l, r); if(r < u || l > v) return {oo, 0}; if(u <= l && r <= v) return st[id]; int mid = l + r >> 1; return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v); } } st; void dfs(int u, int par) { mx_dep[u] = 0; for(auto v:g[u]) { if(v == par) continue; dep[v] = dep[u] + 1; dfs(v, u); maxi(mx_dep[u], mx_dep[v] + 1); } } void dfs2(int u, int par) { auto tmp = st.get(1, 1, n, 1, dep[u] - mx_dep[u] - 1); if(tmp.mn == 0) maxi(res[u], tmp.cnt); for(auto v:g[u]) { if(v == par) continue; st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, 1); } for(auto v:g[u]) { if(v == par) continue; st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, -1); dfs2(v, u); st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, 1); } for(auto v:g[u]) { if(v == par) continue; st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, -1); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>m; for(int i = 1; i < n; i++) { cin>>u>>v; g[u].pb(v); g[v].pb(u); } for(int i = 1; i <= n; i++) cin>>a[i]; dep[1] = 1; dfs(1, 0); int mx = -1, l = 0; for(int i = 1; i <= n; i++) { if(maxi(mx, dep[i])) l = i; } dep[l] = 1; dfs(l, 0); mx = -1; int r = 0; for(int i = 1; i <= n; i++) { if(maxi(mx, dep[i])) r = i; } st.build(1, 1, n); dep[l] = 1; dfs(l, 0); dfs2(l, 0); dep[r] = 1; dfs(r, 0); dfs2(r, 0); for(int i = 1; i <= n; i++) cout<<min(m, res[i])<<"\n"; return 0; }

Compilation message (stderr)

joi2019_ho_t5.cpp: In member function 'void ST::build(int, int, int)':
joi2019_ho_t5.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = l + r >> 1;
      |                   ~~^~~
joi2019_ho_t5.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
joi2019_ho_t5.cpp: In member function 'ST::node ST::get(int, int, int, int, int)':
joi2019_ho_t5.cpp:78:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...