Submission #537412

#	Time	Username	Problem	Language	Result	Execution time	Memory
537412		fhvirus	Capital City (JOI20_capital_city)	C++17	100 / 100	643 ms	134368 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int, int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) LKJ("\033[1;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a != b) cerr << *a << " \n"[(a = next(a)) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

const int kN = 200002;
const int kL = 18;

int N, K, C[kN];
vector<int> adj[kN], town[kN];
int cityLCA[kN];

namespace LCA {

int dep[kN], anc[kL][kN];
void dfs(int u, int p) {
	anc[0][u] = p;
	for (const int& v: adj[u]) {
		if (v == p) continue;
		dep[v] = dep[u] + 1;
		dfs(v, u);
	}
}
void init() {
	dfs(1, 1);
	for (int l = 1; l < kL; ++l)
		for (int i = 1; i <= N; ++i)
			anc[l][i] = anc[l - 1][anc[l - 1][i]];
}
int getLCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int d = dep[u] - dep[v], l = kL - 1; l >= 0; --l)
		if (d >> l & 1) u = anc[l][u];
	if (u == v) return u;
	for (int l = kL - 1; l >= 0; --l)
		if (anc[l][u] != anc[l][v]) {
			u = anc[l][u];
			v = anc[l][v];
		}
	return anc[0][u];
}

} // namespace LCA

namespace HLD {

int siz[kN], in[kN], ou[kN], tot;
int par[kN], head[kN], at[kN];

void dfs_siz(int u, int p) {
	par[u] = p;
	siz[u] = 1;
	for (int &v: adj[u]) {
		if (v == p) continue;
		dfs_siz(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[adj[u][0]])
			swap(v, adj[u][0]);
	}
}
void dfs_chain(int u, int h) {
	in[u] = ++tot;
	head[u] = h;
	for (const int& v: adj[u]) {
		if (v == par[u]) continue;
		dfs_chain(v, (v == adj[u][0] ? h : v));
	}
	ou[u] = tot;
}
void init() {
	dfs_siz(1, 1);
	dfs_chain(1, 1);
	for (int i = 1; i <= N; ++i)
		at[in[i]] = i;
}
vector<pii> get(int u, int v) {
	// go from u to v, v is par of u
	vector<pii> ans;
	while (head[u] != head[v]) {
		ans.pb(in[head[u]], in[u]);
		u = par[head[u]];
	}
	ans.pb(in[v], in[u]);
	return ans;
}

} // namespace HLD

struct SGT {
	int n, tot; vector<int> val;
	vector<vector<int>> adj;
	void init(int i, int l, int r) {
		if (l == r) {
			val[i] = C[HLD::at[l]];
			debug(l, r, val[i]);
			return;
		}
		val[i] = ++tot;
		debug(l, r, val[i]);
		int m = (l + r) / 2;
		init(i * 2, l, m);
		init(i * 2 + 1, m + 1, r);
	}
	void build(int i, int l, int r) {
		if (l == r) {
			return;
		}
		adj[val[i]].pb(val[i * 2]);
		adj[val[i]].pb(val[i * 2 + 1]);
		int m = (l + r) / 2;
		build(i * 2, l, m);
		build(i * 2 + 1, m + 1, r);
	}
	SGT (int _n): n(_n), val(n * 4 + 4), tot(K) {
		init(1, 1, n);
		adj.assign(tot + 1, vector<int>());
		build(1, 1, n);
	}
	void add(int i, int l, int r, int qv, int ql, int qr) {
		if (ql <= l and r <= qr) {
			adj[qv].pb(val[i]);
			return;
		}
		int m = (l + r) / 2;
		if (ql <= m) add(i * 2, l, m, qv, ql, qr);
		if (m < qr) add(i * 2 + 1, m + 1, r, qv, ql, qr);
	}
	void add(int qv, int ql, int qr) { add(1, 1, n, qv, ql, qr); }
};

struct SCC {
	int n, tot, sccnt, top;
	vector<vector<int>> adj;
	vector<int> pre, low;
	vector<int> ins, stk;
	vector<int> scc;
	vector<set<int>> has;
	SCC (const vector<vector<int>>& init):
		n(init.size()), tot(0), sccnt(0), top(0), adj(init), pre(n, 0), low(n, 0),
		ins(n, 0), stk(n, 0), scc(n, 0), has(n) {}
	void tarjan(int u) {
		low[u] = pre[u] = ++tot;
		ins[u] = true; stk[++top] = u;
		for (const int& v: adj[u]) {
			if (pre[v] == 0) {
				tarjan(v);
				low[u] = min(low[u], low[v]);
			} else if (ins[v])
				low[u] = min(low[u], pre[v]);
		}
		if (low[u] == pre[u]) {
			++sccnt;
			int v;
			do {
				v = stk[top--];
				scc[v] = sccnt;
				ins[v] = false;
				if (v <= K)
					has[sccnt].insert(v);
			} while (v != u);
		}
	}
	int solve() {
		for (int i = 1; i < n; ++i)
			if (pre[i] == 0) tarjan(i);

		vector<int> oudeg(n, 0);
		for (int i = 1; i < n; ++i)
			for (const int& j: adj[i])
				if (scc[i] != scc[j])
					++oudeg[scc[i]];
		int ans = n + n;
		for (int i = 1; i <= sccnt; ++i)
			if (oudeg[i] == 0)
				ans = min(ans, (int) has[i].size());
		return ans;
	}
};

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> K;
	for (int A, B, i = 1; i < N; ++i) {
		cin >> A >> B;
		adj[A].pb(B);
		adj[B].pb(A);
	}
	for (int i = 1; i <= N; ++i) {
		cin >> C[i];
		town[C[i]].pb(i);
	}

	LCA::init();

	for (int i = 1; i <= K; ++i) {
		cityLCA[i] = town[i][0];
		for (int j = 1; j < town[i].size(); ++j)
			cityLCA[i] = LCA::getLCA(cityLCA[i], town[i][j]);
		//debug(i, cityLCA[i]);
	}

	HLD::init();
	for (int i = 1; i <= N; ++i) {
		debug(i, HLD::at[i]);
	}

	SGT sgt(N);

	for (int i = 1; i <= N; ++i) {
		int c = C[i];
		int u = HLD::at[i];
		int v = HLD::at[cityLCA[c]];
		debug(i, c, u, v);
		vector<pii> rs = HLD::get(i, cityLCA[c]);
		for (const auto& [l, r]: rs) {
			sgt.add(c, l, r);
			debug(l, r);
		}
	}

	for (int i = 1; i <= sgt.tot; ++i) {
		debug(i);
		auto &v = sgt.adj[i];
		sort(AI(v));
		v.erase(unique(AI(v)), end(v));
		OI(AI(sgt.adj[i]));
	}

	SCC scc(sgt.adj);
	cout << scc.solve() - 1 << '\n';

	return 0;
}

Compilation message (stderr)

capital_city.cpp: In member function 'void SGT::init(int, int, int)':
capital_city.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
capital_city.cpp:107:4: note: in expansion of macro 'debug'
  107 |    debug(l, r, val[i]);
      |    ^~~~~
capital_city.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
capital_city.cpp:111:3: note: in expansion of macro 'debug'
  111 |   debug(l, r, val[i]);
      |   ^~~~~
capital_city.cpp: In constructor 'SGT::SGT(int)':
capital_city.cpp:102:26: warning: 'SGT::val' will be initialized after [-Wreorder]
  102 |  int n, tot; vector<int> val;
      |                          ^~~
capital_city.cpp:102:9: warning:   'int SGT::tot' [-Wreorder]
  102 |  int n, tot; vector<int> val;
      |         ^~~
capital_city.cpp:126:2: warning:   when initialized here [-Wreorder]
  126 |  SGT (int _n): n(_n), val(n * 4 + 4), tot(K) {
      |  ^~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:210:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |   for (int j = 1; j < town[i].size(); ++j)
      |                   ~~^~~~~~~~~~~~~~~~
capital_city.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
capital_city.cpp:217:3: note: in expansion of macro 'debug'
  217 |   debug(i, HLD::at[i]);
      |   ^~~~~
capital_city.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
capital_city.cpp:226:3: note: in expansion of macro 'debug'
  226 |   debug(i, c, u, v);
      |   ^~~~~
capital_city.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
capital_city.cpp:230:4: note: in expansion of macro 'debug'
  230 |    debug(l, r);
      |    ^~~~~
capital_city.cpp:224:7: warning: unused variable 'u' [-Wunused-variable]
  224 |   int u = HLD::at[i];
      |       ^
capital_city.cpp:225:7: warning: unused variable 'v' [-Wunused-variable]
  225 |   int v = HLD::at[cityLCA[c]];
      |       ^
capital_city.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
capital_city.cpp:235:3: note: in expansion of macro 'debug'
  235 |   debug(i);
      |   ^~~~~
capital_city.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define OI(...) 0
      |                 ^
capital_city.cpp:239:3: note: in expansion of macro 'OI'
  239 |   OI(AI(sgt.adj[i]));
      |   ^~

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