oj.uz

Submission #883035

# Submission time Handle Problem Language Result Execution time Memory
883035 2023-12-04T12:37:04 Z 8pete8 Capital City (JOI20_capital_city) C++14
1 / 100
 310 ms 95316 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(group[i].size()&&!vis[i])tarjan(i);
	cout<<((ans==inf)?0:ans);
	return 0;
}

Compilation message

capital_city.cpp: In function 'void tarjan(long long int)':
capital_city.cpp:71:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   71 |   if(st.empty()||st.top()==cur&&adj[cur].size())yes=false;
      |                  ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
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 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 5 ms 21116 KB Output is correct
6 Correct 4 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 21072 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 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 5 ms 21116 KB Output is correct
6 Correct 4 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 21072 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 5 ms 23132 KB Output is correct
12 Correct 5 ms 23132 KB Output is correct
13 Correct 5 ms 23132 KB Output is correct
14 Correct 5 ms 23132 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct
16 Correct 5 ms 23248 KB Output is correct
17 Correct 5 ms 23132 KB Output is correct
18 Correct 5 ms 23132 KB Output is correct
19 Correct 5 ms 23240 KB Output is correct
20 Correct 5 ms 23132 KB Output is correct
21 Correct 5 ms 23128 KB Output is correct
22 Correct 5 ms 23332 KB Output is correct
23 Correct 7 ms 23200 KB Output is correct
24 Correct 6 ms 23236 KB Output is correct
25 Correct 5 ms 23356 KB Output is correct
26 Correct 5 ms 23132 KB Output is correct
27 Correct 5 ms 23132 KB Output is correct
28 Correct 5 ms 23128 KB Output is correct
29 Correct 6 ms 23132 KB Output is correct
30 Incorrect 5 ms 23116 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 95316 KB Output is correct
2 Correct 107 ms 95060 KB Output is correct
3 Correct 310 ms 95060 KB Output is correct
4 Correct 108 ms 95148 KB Output is correct
5 Correct 236 ms 94304 KB Output is correct
6 Correct 112 ms 95284 KB Output is correct
7 Correct 214 ms 93760 KB Output is correct
8 Correct 101 ms 94404 KB Output is correct
9 Correct 175 ms 92496 KB Output is correct
10 Incorrect 174 ms 91620 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 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 5 ms 21116 KB Output is correct
6 Correct 4 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 21072 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 5 ms 23132 KB Output is correct
12 Correct 5 ms 23132 KB Output is correct
13 Correct 5 ms 23132 KB Output is correct
14 Correct 5 ms 23132 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct
16 Correct 5 ms 23248 KB Output is correct
17 Correct 5 ms 23132 KB Output is correct
18 Correct 5 ms 23132 KB Output is correct
19 Correct 5 ms 23240 KB Output is correct
20 Correct 5 ms 23132 KB Output is correct
21 Correct 5 ms 23128 KB Output is correct
22 Correct 5 ms 23332 KB Output is correct
23 Correct 7 ms 23200 KB Output is correct
24 Correct 6 ms 23236 KB Output is correct
25 Correct 5 ms 23356 KB Output is correct
26 Correct 5 ms 23132 KB Output is correct
27 Correct 5 ms 23132 KB Output is correct
28 Correct 5 ms 23128 KB Output is correct
29 Correct 6 ms 23132 KB Output is correct
30 Incorrect 5 ms 23116 KB Output isn't correct
31 Halted 0 ms 0 KB -