Submission #537356

#	Time	Username	Problem	Language	Result	Execution time	Memory
537356		Haruto810198	Capital City (JOI20_capital_city)	C++17	30 / 100	1989 ms	105356 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n, k;
vi edge[MAX];
int icity[MAX];

int ts;
int arr[MAX];
vi occ[MAX];

set<int> st;
int dpl[MAX], dpr[MAX];
int stl[MAX][20], str[MAX][20];
vector<pii> segs;
int res;

void dfs(int v, int pv){
	ts++;
	arr[ts] = icity[v];
	occ[arr[ts]].pb(ts);
	for(int i : edge[v]){
		if(i == pv) continue;
		dfs(i, v);
	}
}

inline pii query(int l, int r){
	int rk = __lg(r - l + 1);
	return mkp(min(stl[l][rk], stl[r - (1<<rk) + 1][rk]), max(str[l][rk], str[r -(1<<rk) + 1][rk]));
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	FOR(i, 1, n-1, 1){
		int u, v;
		cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	FOR(i, 1, n, 1){
		cin>>icity[i];
	}

	int root = 0;
	FOR(i, 1, n, 1){
		if(szof(edge[i]) == 1) root = i;
	}

	dfs(root, root);
	
	FOR(i, 1, n, 1){
		dpl[i] = dpr[i] = i;	
	}
	
	FOR(i, 1, n, 1){
		dpl[i] = occ[arr[i]].front();
		dpr[i] = occ[arr[i]].back();
		//cerr<<"["<<dpl[i]<<", "<<dpr[i]<<"]"<<endl;
	}

	FOR(owo, 1, 19, 1){
		// build stl, str
		FOR(i, 1, n, 1){
			stl[i][0] = dpl[i];
			str[i][0] = dpr[i];
		}

		FOR(j, 1, 19, 1){
			FOR(i, 1, n, 1){
				int ii = i + (1<<(j-1));
				if(ii <= n){
					stl[i][j] = min(stl[i][j-1], stl[ii][j-1]);
					str[i][j] = max(str[i][j-1], str[ii][j-1]);
				}
				else{
					stl[i][j] = stl[i][j-1];
					str[i][j] = str[i][j-1];
				}
			}
		}

		// update dpl, dpr
		FOR(i, 1, n, 1){
			pii Q = query(dpl[i], dpr[i]);
			dpl[i] = Q.F;
			dpr[i] = Q.S;
		}
	}
	
	FOR(i, 1, n, 1){
		//cerr<<"["<<dpl[i]<<", "<<dpr[i]<<"]"<<endl;
	}

	res = INF;
	FOR(i, 1, n, 1){
		segs.eb(dpl[i], dpr[i]);
	}
	sort(segs.begin(), segs.end(), [&](pii a, pii b){
		if(a.F == b.F) return (a.S > b.S);
		return (a.F < b.F);
	});
	
	vector<pii> stk;
	for(pii p : segs){
		if(stk.empty()) stk.pb(p);
		else if(stk.back().F <= p.F and p.S <= stk.back().S){
			stk.pop_back();
			stk.pb(p);
		}
		else{
			stk.pb(p);
		}
	}

	for(pii p : stk){
		st.clear();
		FOR(i, p.F, p.S, 1){
			st.insert(arr[i]);
		}
		res = min(res, szof(st));
	}

	cout<<res - 1<<'\n';
	
	return 0;

}

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