Submission #1280006

#TimeUsernameProblemLanguageResultExecution timeMemory
1280006phuocrucppCapital City (JOI20_capital_city)C++20
11 / 100
204 ms101760 KiB
/*ㅤ∧_∧  ( ・∀・)  ( つ┳⊃ ε (_)へ⌒ヽフ (  ( ・ω・) ◎―◎ ⊃ ⊃ BePhuongSuperSuwi From TK4 - CHT ㅤㅤ/ ⌒\____   /・   )  \  /ノへ ノ    /| ノ   \\ |/_/_/*/ #include<bits/stdc++.h> #define task "main" //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define endl '\n' //#define int long long #define pb push_back #define fi first #define se second #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii, ii> #define base 341 #define MASK(i) (1ll << i) #define oo 2e9 using namespace std; //using namespace __gnu_pbds; const int maxn = 2e5 + 5; const int lg = 18; int n, k, val[maxn], h[maxn], par[maxn][lg + 2]; vector <int> g[maxn], c[maxn]; void dfs(int u, int p) { for (int x : g[u]) { if (x == p) continue; h[x] = h[u] + 1; par[x][0] = u; dfs(x, u); } } int lca(int u, int v) { if (h[u] < h[v]) swap(u,v); for (int i = lg; i >= 0; i--) { if ((h[u] - h[v]) >= MASK(i)) u = par[u][i]; } if (u == v) return u; for (int i = lg; i >= 0; i--) { if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } } return par[u][0]; } void prelca() { dfs(1, -1); for (int j = 1; j <= lg; j++) { for (int i = 1; i <= n; i++) { par[i][j] = par[par[i][j-1]][j-1]; } } } namespace giai2{ vector <int> adj[maxn]; int lim = 0; vector <ii> ed; int tin[maxn], tour[maxn], timer = 0; struct HLD{ int sz[maxn], Head[maxn], Pos[maxn], Id[maxn], chain, timer = 0, h[maxn], par[maxn]; int st[maxn * 4]; void build(int id, int l, int r) { st[id] = ++lim; if (l == r) { adj[st[id]].pb(val[tour[l]]); ed.pb({st[id], val[tour[l]]}); // cout << st[id] << " " << val[tour[l]] << endl; return; } int m = (l + r) / 2; build(id * 2, l, m); build(id * 2 + 1, m + 1, r); adj[st[id]].pb(st[id * 2]); adj[st[id]].pb(st[id * 2 + 1]); ed.pb({st[id], st[id * 2]}); ed.pb({st[id], st[id * 2 + 1]}); // cout << st[id] << " " << st[id * 2] << endl; // cout << st[id] << " " << st[id * 2 + 1] << endl; } void dfs(int u, int p) { sz[u] = 1; for (int x : g[u]) { if (x == p) continue; h[x] = h[u] + 1; par[x] = u; dfs(x, u); sz[u] += sz[x]; } } void hld(int u, int p) { if (!Head[chain]) { Head[chain] = u; } Id[u] = chain; Pos[u] = tin[u] = ++timer; tour[timer] = u; int nxt = 0; for (int x : g[u]) { if (x == p) continue; if (nxt == 0 || sz[nxt] < sz[x]) nxt = x; } if (nxt) hld(nxt, u); for (int x : g[u]) { if (x == p || x == nxt) continue; chain++; hld(x, u); } } void update(int id, int l, int r, int u, int v, int idx) { if (u > r || v < l) return; if (l >= u && r <= v) { adj[idx].pb(st[id]); ed.pb({idx, st[id]}); // cout << idx << " " << st[id] << endl; return; } int m = (l + r) / 2; update(id * 2, l, m, u, v, idx); update(id * 2 + 1, m + 1, r, u, v, idx); } void upd(int u, int v, int idx) { while (Id[u] != Id[v]) { if (h[Head[Id[u]]] > h[Head[Id[v]]]) swap(u,v); update(1,1,n,Pos[Head[Id[v]]], Pos[v], idx); v = par[Head[Id[v]]]; } if (h[u] > h[v]) swap(u,v); update(1,1,n,Pos[u], Pos[v], idx); } void init() { timer = 0; dfs(1, -1); chain = 1; hld(1, -1); build(1, 1, n); } } hld1; int d[maxn], low[maxn], ssc[maxn], tplt, sz[maxn]; bool in[maxn]; stack <int> stk; void dfs(int u) { d[u] = low[u] = ++timer; stk.push(u); for (int x : adj[u]) { if (d[x] == 0) { dfs(x); low[u] = min(low[u], low[x]); } else if (!in[x]) { low[u] = min(low[u], d[x]); } } if (d[u] == low[u]) { int p; tplt++; do{ p = stk.top(); in[p] = true; ssc[p] = tplt; if (p <= k) sz[tplt]++; stk.pop(); }while(p!=u); } } bool ok[maxn]; bool ss(int x, int y) { return tin[x] < tin[y]; } void solve() { for (int i = 1; i <= n; i++) c[val[i]].pb(i); lim = k; hld1.init(); // for (int i = 1; i <= n; i++) cout << tin[i] << endl; // cout << lim << endl; for (int i = 1; i <= k; i++){ sort(c[i].begin(), c[i].end(), ss); for (int j = 0; j < c[i].size() - 1; j++) { hld1.upd(c[i][j], c[i][j + 1], i); // cout << i << " " << c[i][j] << " " << c[i][j + 1] << endl; } } timer = 0; for (int i = 1; i <= lim; i++) { if (!d[i]) dfs(i); } // // cout << tplt << endl; for (int u = 1; u <= lim; u++) { for (int v : adj[u]) { int l = ssc[u], r = ssc[v]; if (l != r) { ok[l] = 1; } } } int mini = oo; for (int i = 1; i <= tplt; i++) { if (!ok[i]) { mini = min(mini, sz[i] - 1); //cout << "ssc " << i << " " << sz[i] << endl; } } cout << mini; } } main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n >> k; for (int i = 1; i < n; i++) { int l, r; cin >> l >> r; g[l].pb(r); g[r].pb(l); } prelca(); for (int i = 1; i <= n; i++) { cin >> val[i]; } // giai2::solve(); giai2::solve(); // if (n <= 2000) giai1::solve(); // else giai2::solve(); }

Compilation message (stderr)

capital_city.cpp:237:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  237 | main() {
      | ^~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:240:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:241:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...