oj.uz

Submission #883032

# Submission time Handle Problem Language Result Execution time Memory
883032 2023-12-04T12:33:56 Z 8pete8 Capital City (JOI20_capital_city) C++14
1 / 100
 264 ms 98940 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
const int mod=1e9+7,mxn=2e5+5,lg=30,inf=1e18,minf=-1e18;
// ->, <-, all node that follow in component||node of that component
int n,k;
int h[mxn+10],up[mxn+10][lg+5],g[mxn+10],gl[mxn+10],low[mxn+10],disc[mxn+10];
vector<int>adj[mxn+10],group[mxn+10],adj2[mxn+10];
void dfs(int cur,int p){
	for(auto i:adj[cur]){
		if(i==p)continue;
		h[i]=h[cur]+1;
		up[i][0]=cur;
		dfs(i,cur);
	}
}
int lca(int a,int b){
	if(h[a]<h[b])swap(a,b);
	int k=h[a]-h[b];
	for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i];
	if(a==b)return a;
	for(int i=lg;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
	return up[a][0];
}
bitset<mxn+10>on,vis;
stack<int>st;
int t=0,ans=inf;
void tarjan(int cur){
	vis[cur]=true;
	low[cur]=disc[cur]=++t;
	st.push(cur);
	on[cur]=true;
	for(auto i:adj2[cur]){
		if(!disc[i])tarjan(i),low[cur]=min(low[cur],low[i]);
		else if(on[i])low[cur]=min(low[cur],low[i]);
	}
	if(disc[cur]==low[cur]){
		bool yes=true;
		on[cur]=false;
		int cnt=1;
		if(!st.empty()&&st.top()==cur&&adj[cur].size())yes=false;
		while(!st.empty()&&st.top()!=cur){
			if(on[st.top()])cnt++;
			on[st.top()]=false;
			st.pop();
		}
		if(!st.empty())st.pop();
		if(yes)ans=min(ans,cnt-1);
	}
}
int32_t main(){
	fastio
	cin>>n>>k;
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++)cin>>g[i],group[g[i]].pb(i);
	for(int i=1;i<=lg;i++)up[1][i]=1;
	for(int i=1;i<=lg;i++)for(int j=1;j<=n;j++)up[j][i]=up[up[j][i-1]][i-1];
	for(int i=1;i<=k;i++){
		if(group[i].empty())continue;
		int node=group[i][0];
		for(int j=1;j<group[i].size();j++)node=lca(node,group[i][j]);
		gl[i]=node;
	}
	for(int i=1;i<=n;i++)if(g[up[i][0]]!=g[i]&&i!=gl[g[i]])adj2[g[i]].pb(g[up[i][0]]);
	for(int i=1;i<=k;i++)if(!vis[i])tarjan(i);
	cout<<ans;
	return 0;
}

Compilation message

capital_city.cpp: In function 'int32_t main()':
capital_city.cpp:96:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int j=1;j<group[i].size();j++)node=lca(node,group[i][j]);
      |               ~^~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 6 ms 21108 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21080 KB Output is correct
6 Correct 6 ms 21084 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 5 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 6 ms 21108 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21080 KB Output is correct
6 Correct 6 ms 21084 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 5 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 5 ms 23296 KB Output is correct
12 Correct 5 ms 23128 KB Output is correct
13 Correct 5 ms 23360 KB Output is correct
14 Correct 6 ms 23168 KB Output is correct
15 Correct 5 ms 23140 KB Output is correct
16 Correct 5 ms 23132 KB Output is correct
17 Correct 5 ms 23128 KB Output is correct
18 Correct 6 ms 23132 KB Output is correct
19 Correct 5 ms 23352 KB Output is correct
20 Correct 6 ms 23128 KB Output is correct
21 Correct 5 ms 23132 KB Output is correct
22 Correct 6 ms 23388 KB Output is correct
23 Correct 6 ms 23388 KB Output is correct
24 Correct 5 ms 23388 KB Output is correct
25 Correct 6 ms 23132 KB Output is correct
26 Correct 6 ms 23388 KB Output is correct
27 Correct 5 ms 23344 KB Output is correct
28 Correct 5 ms 23132 KB Output is correct
29 Correct 5 ms 23132 KB Output is correct
30 Incorrect 6 ms 23132 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 98940 KB Output is correct
2 Correct 121 ms 98824 KB Output is correct
3 Correct 222 ms 98824 KB Output is correct
4 Correct 109 ms 98900 KB Output is correct
5 Correct 239 ms 97876 KB Output is correct
6 Correct 110 ms 98640 KB Output is correct
7 Correct 264 ms 97412 KB Output is correct
8 Correct 107 ms 98080 KB Output is correct
9 Correct 218 ms 96104 KB Output is correct
10 Incorrect 170 ms 95076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 6 ms 21108 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21080 KB Output is correct
6 Correct 6 ms 21084 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 21084 KB Output is correct
9 Correct 5 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 5 ms 23296 KB Output is correct
12 Correct 5 ms 23128 KB Output is correct
13 Correct 5 ms 23360 KB Output is correct
14 Correct 6 ms 23168 KB Output is correct
15 Correct 5 ms 23140 KB Output is correct
16 Correct 5 ms 23132 KB Output is correct
17 Correct 5 ms 23128 KB Output is correct
18 Correct 6 ms 23132 KB Output is correct
19 Correct 5 ms 23352 KB Output is correct
20 Correct 6 ms 23128 KB Output is correct
21 Correct 5 ms 23132 KB Output is correct
22 Correct 6 ms 23388 KB Output is correct
23 Correct 6 ms 23388 KB Output is correct
24 Correct 5 ms 23388 KB Output is correct
25 Correct 6 ms 23132 KB Output is correct
26 Correct 6 ms 23388 KB Output is correct
27 Correct 5 ms 23344 KB Output is correct
28 Correct 5 ms 23132 KB Output is correct
29 Correct 5 ms 23132 KB Output is correct
30 Incorrect 6 ms 23132 KB Output isn't correct
31 Halted 0 ms 0 KB -