Submission #428452

#	Time	Username	Problem	Language	Result	Execution time	Memory
428452		amunduzbaev	Capital City (JOI20_capital_city)	C++14	100 / 100	530 ms	91168 KiB

capital_city

/* made by amunduzbaev */
 
#include "bits/stdc++.h"
 
using namespace std;
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update>;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
#define int long long
#define degub(x) cout<<#x<<" : "<<x<<"\n"
#define GG cout<<"here"<<endl;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
int lca[N][20], tin[N], tout[N], llca[N];
int ns[N], d[N];
vii edges[N], qwe[N];

void predfs(int u, int p = -1){
	tin[u] = t++;
	for(int i=1;i<20;i++) lca[u][i] = lca[lca[u][i-1]][i-1];
	for(auto x : qwe[u]){
		if(x == p) continue;
		lca[x][0] = u, d[x] = d[u] + 1;
		if(a[x] == a[u]) ns[x] = ns[u];
		else ns[x] = u;
		predfs(x, u);
	} tout[u] = t - 1;
}

bool par(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int LCA(int a, int b){
	if(par(a, b)) return a;
	if(par(b, a)) return b;
	for(int i=19;i>=0;i--) if(!par(lca[a][i], b)) a = lca[a][i];
	a = lca[a][0];
	return a;
}

void dfs(int u, int p = -1){
	if(d[ns[u]] >= d[llca[a[u]]] && ns[u]) edges[a[u]].pb(a[ns[u]]);
	for(auto x : qwe[u]){
		if(x == p) continue;
		dfs(x, u);
	}
}
int low[N], up[N], used[N], cmp[N], last, cost[N];
stack<int> ss;
vv<vii> tt;

void scc_dfs(int u){ used[u] = 1;
	low[u] = up[u] = t++;
	ss.push(u);
	for(auto x : edges[u]){
		if(used[x] && !cmp[x]) umin(low[u], up[x]);
		else if(!used[x]) scc_dfs(x), umin(low[u], low[x]);
	}
	
	if(low[u] == up[u]){
		int cur; ++last;
		tt.pb({});
		do{
			cur = ss.top(); ss.pop();
			tt.back().pb(cur);
			cmp[cur] = last;
		}while(cur != u); 
		cost[last] = sz(tt.back());
	}
}

vii top;
void topsort(int u){ used[u] = 1;
	for(auto x : qwe[u]){
		if(!used[x]) topsort(x);
	} top.pb(u);
}

void solve(int t_case){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		qwe[a].pb(b), qwe[b].pb(a);
	} for(int i=1;i<=n;i++) cin>>a[i];
	predfs(1);
	mem(llca, -1);
	for(int i=1;i<=n;i++){
		if(~llca[a[i]]) llca[a[i]] = LCA(llca[a[i]], i);
		else llca[a[i]] = i;
	} dfs(1);
	for(int i=1;i<=k;i++){
		set<int> ss;
		for(auto x : edges[i]) ss.insert(x);
		edges[i].clear();
		for(auto x : ss) edges[i].pb(x);
		//~ cout<<i<<" : ";
		//~ for(auto x : edges[i]) cout<<x<<" ";
		//~ cout<<endl;
	} 
	//~ for(int i=1;i<=n;i++) cout<<ns[i]<<" ";
	//~ cout<<endl;
	t = 0;
	
/*

6 3
2 1
3 5
6 2
3 4
2 3
1 3 1 2 3 2

*/

	
	for(int i=1;i<=k;i++){
		if(used[i]) continue;
		scc_dfs(i);
	}
	//~ GG
	for(int i=1;i<=n;i++) qwe[i].clear();
	for(auto xx : tt){
		for(auto u : xx){
			for(auto x : edges[u]){
				qwe[cmp[u]].pb(cmp[x]);
			} 
		}
	}
	
	//~ for(int i=1;i<=k;i++) cout<<cmp[i]<<" ";
	//~ cout<<"\n";
	
	//~ GG
	n = last; mem(used, 0);
	for(int i=1;i<=n;i++){
		set<int> ss;
		for(auto x : qwe[i]) ss.insert(x);
		qwe[i].clear();
		ss.erase(i);
		for(auto x : ss) qwe[i].pb(x);
		//~ cout<<i<<" : ";
		
		//~ for(auto x : ss) cout<<x<<" ";
		//~ cout<<"\n";
	}
	
	res = inf;
	for(int i=1;i<=n;i++) if(!used[i]) topsort(i);
	for(auto u : top){
		for(auto x : qwe[u]) cost[u] += cost[x];
		umin(res, cost[u]);
	} cout<<res - 1<<"\n";
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void usaco(std::string)':
capital_city.cpp:38:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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