Submission #537400

#	Time	Username	Problem	Language	Result	Execution time	Memory
537400		8e7	Capital City (JOI20_capital_city)	C++17	0 / 100	263 ms	25184 KiB

capital_city

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn];
int c[maxn], dep[maxn], f[maxn];
pii ran[maxn];
void dfs(int n, int par, int d) {
	dep[n] = d;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d+1);
		}
	}
}
struct segtree{
	int seg[4* maxn];
	void modify(int cur, int l, int r, int ind, int val) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = val;
			return;
		}
		int m = (l + r) / 2;
		if (ind < m)modify(cur*2, l, m, ind, val);
		else modify(cur*2+1, m, r, ind, val);
		seg[cur] = min(seg[cur*2], seg[cur*2+1]);
	}
	int query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return 1<<30;
		if (ql <= l && qr >= r) {
			return seg[cur];
		}
		int m = (l + r) / 2;
		return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
	}
} tr, rig;
struct BIT{
	int bit[maxn];
	void modify(int ind, int val) {
		if (ind == 0) return;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bit;
int prv[maxn];
int main() {
	io
	int n, K;
	cin >> n >> K;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);	
	}
	for (int i = 1;i <= n;i++) {
		if (adj[i].size() == 1) {
			dfs(i, 0,1);
			break;
		}
	}
	for (int i = 1;i <= K;i++) ran[i] = {n+1, 0};
	for (int i = 1;i <= n;i++) {
		cin >> c[dep[i]];
		ran[c[dep[i]]] = make_pair(min(ran[c[dep[i]]].ff, dep[i]), max(ran[c[dep[i]]].ss, dep[i]));
	}
	for (int i = 1;i <= K;i++) debug(ran[i].ff, ran[i].ss);
	
	int ans = n+1;	
	for (int i = 1;i <= n;i++) {
		int mi = tr.query(1, 1, n+1, ran[c[i]].ff, i);	
		f[i] = min(ran[c[i]].ff, mi);		
		tr.modify(1, 1, n+1, i, f[i]);
		rig.modify(1, 1, n+1, i, -ran[c[i]].ss);	
	}
	pary(f + 1, f + n + 1);
	for (int i = 1;i <=	n;i++) {
		int r = -rig.query(1, 1, n+1, f[i], i);
		bit.modify(prv[c[i]], -1);
		bit.modify(i, 1);
		prv[c[i]] = i;
		if (i == ran[c[i]].ss && r <= i) {
			ans = min(ans, bit.query(i) - bit.query(f[i] - 1) - 1);
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
capital_city.cpp:88:29: note: in expansion of macro 'debug'
   88 |  for (int i = 1;i <= K;i++) debug(ran[i].ff, ran[i].ss);
      |                             ^~~~~
capital_city.cpp:13:19: warning: statement has no effect [-Wunused-value]
   13 | #define pary(...) 0
      |                   ^
capital_city.cpp:97:2: note: in expansion of macro 'pary'
   97 |  pary(f + 1, f + n + 1);
      |  ^~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59