Submission #245433

#	Time	Username	Problem	Language	Result	Execution time	Memory
245433		onjo0127	Capital City (JOI20_capital_city)	C++11	30 / 100	241 ms	26308 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 1e9;

struct segtree {
	vector<int> T;
	void upd(int idx, int s, int e, int p, int v) {
		if(p < s || e < p) return;
		if(s == e) {
			T[idx] = v;
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, p, v);
		upd(idx*2+1, m+1, e, p, v);
		T[idx] = max(T[idx*2], T[idx*2+1]);
	}
	int get(int idx, int s, int e, int l, int r) {
		if(r < s || e < l) return -INF;
		if(l <= s && e <= r) return T[idx];
		int m = s+e >> 1;
		return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
	}
	void init(int N) {
		T.resize(4*N, -INF);
	}
};

int C[200009], O[200009], L[200009], R[200009], CL[200009], CR[200009], chk[200009];
vector<int> G[200009];

int main() {
	int N, K; scanf("%d%d",&N,&K);
	if(N == 1) return !printf("0");
	for(int i=0; i<N-1; i++) {
		int u, v; scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1; i<=N; i++) {
		scanf("%d", &C[i]);
		L[i] = N; R[i] = 1;
	}
	int x = -1, p = -1;
	for(int i=1; i<=N; i++) if((int)G[i].size() == 1) x = i;
	for(int i=1; i<=N; i++) {
		O[i] = x;
		for(auto& it: G[x]) if(it != p) {
			p = x, x = it;
			break;
		}
	}
	for(int i=1; i<=N; i++) {
		int c = C[O[i]];
		L[c] = min(L[c], i);
		R[c] = max(R[c], i);
	}
	for(int i=1; i<=N; i++) {
		int c = C[O[i]];
		CR[i] = R[c];
		CL[i] = L[c];
	}
	vector<pii> par;
	segtree MXS, MNS;
	MXS.init(N); MNS.init(N);
	for(int i=N; i>=1; i--) {
		if(CL[i] == i) {
			int rm = max(MXS.get(1, 1, N, i, CR[i]), CR[i]);
			int lm = min(-MNS.get(1, 1, N, i, rm), i);
			if(lm == i) par.push_back({lm, rm});
			MXS.upd(1, 1, N, i, rm);
		}
		else MNS.upd(1, 1, N, i, -CL[i]);
	}
	int r = N, l = N+1, ans = INF, cnt = 0;
	for(auto& it: par) {
		int lm, rm; tie(lm, rm) = it;
		while(lm < l) {
			if(chk[C[O[l-1]]] == 0) ++cnt;
			++chk[C[O[l-1]]]; --l;
		}
		while(rm < r) {
			--chk[C[O[r]]];
			if(chk[C[O[r]]] == 0) --cnt;
			--r;
		}
		if(l == lm && r == rm) ans = min(ans, cnt - 1);
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
capital_city.cpp:14:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
capital_city.cpp: In member function 'int segtree::get(int, int, int, int, int)':
capital_city.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
capital_city.cpp: In function 'int main()':
capital_city.cpp:34:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, K; scanf("%d%d",&N,&K);
            ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~

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