#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int vis[200001],vis1[200001],vis2[200001],par[200001],sz[200001],n,c;
vi cit[200001],al[200001];
int tc[200001];
unordered_map<int,int> m,m1;
void dfs(int node,int p,int no)
{
vis1[node]=no;
sz[node]=1;
for(int i=0;i<al[node].size();++i)
{
if(vis[al[node][i]]+vis1[al[node][i]]==0)
{
dfs(al[node][i],node,no);
sz[node]+=sz[al[node][i]];
}
}
}
void dfs2(int node,int p,int no)
{
vis2[node]=no;
par[node]=p;
for(int i=0;i<al[node].size();++i)
{
if(vis[al[node][i]]+vis2[al[node][i]]==0)
dfs2(al[node][i],node,no);
}
}
int tell(int node,int p,int to)
{
for(int i=0;i<al[node].size();++i)
if(al[node][i]!=p&&vis[al[node][i]]==0&&sz[al[node][i]]>to/2)
return(tell(al[node][i],node,to));
return(node);
}
int ins(int node)
{
if(m.find(node)!=m.end())
return(0);
m[node]=1;
int r=0;
if(m1.find(tc[node])==m1.end())
{
m1[tc[node]]=1;
for(int i=0;i<cit[tc[node]].size();++i)
{
if(vis2[cit[tc[node]][i]]!=vis2[node])
return(-1);
r=min(ins(cit[tc[node]][i]),r);
}
}
if(m.find(par[node])==m.end())
r=min(ins(par[node]),r);
return(r);
}
int solve(int node)
{
int co=ins(node);
if(co==-1)
return(c-1);
return(m1.size()-1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>c;
for(int i=0;i<n-1;++i)
{
int f,s;
cin>>f>>s;
al[f].pb(s);
al[s].pb(f);
}
for(int i=0;i<n;++i)
{
int f;
cin>>f;
tc[i+1]=f;
cit[f].pb(i+1);
}
int co=0,ans=c-1,no=1;
while(co!=n)
{
for(int i=1;i<=n;++i)
{
if(vis[i]+vis1[i]==0)
{
dfs(i,i,no);
no++;
int cen=tell(i,i,sz[i]);
vis[cen]=1;
co++;
dfs2(cen,cen,no);
no++;
ans=min(solve(cen),ans);
m.clear();
m1.clear();
}
}
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
}
cout<<ans<<endl;
return 0;
}
Compilation message
capital_city.cpp: In function 'void dfs(int, int, int)':
capital_city.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
capital_city.cpp: In function 'void dfs2(int, int, int)':
capital_city.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int tell(int, int, int)':
capital_city.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int ins(int)':
capital_city.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cit[tc[node]].size();++i)
~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11392 KB |
Output is correct |
2 |
Correct |
6 ms |
11392 KB |
Output is correct |
3 |
Correct |
7 ms |
11264 KB |
Output is correct |
4 |
Correct |
6 ms |
11392 KB |
Output is correct |
5 |
Correct |
6 ms |
11264 KB |
Output is correct |
6 |
Correct |
6 ms |
11392 KB |
Output is correct |
7 |
Correct |
7 ms |
11264 KB |
Output is correct |
8 |
Correct |
7 ms |
11264 KB |
Output is correct |
9 |
Correct |
7 ms |
11264 KB |
Output is correct |
10 |
Correct |
7 ms |
11264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11392 KB |
Output is correct |
2 |
Correct |
6 ms |
11392 KB |
Output is correct |
3 |
Correct |
7 ms |
11264 KB |
Output is correct |
4 |
Correct |
6 ms |
11392 KB |
Output is correct |
5 |
Correct |
6 ms |
11264 KB |
Output is correct |
6 |
Correct |
6 ms |
11392 KB |
Output is correct |
7 |
Correct |
7 ms |
11264 KB |
Output is correct |
8 |
Correct |
7 ms |
11264 KB |
Output is correct |
9 |
Correct |
7 ms |
11264 KB |
Output is correct |
10 |
Correct |
7 ms |
11264 KB |
Output is correct |
11 |
Correct |
17 ms |
11520 KB |
Output is correct |
12 |
Correct |
12 ms |
11520 KB |
Output is correct |
13 |
Correct |
11 ms |
11520 KB |
Output is correct |
14 |
Correct |
12 ms |
11520 KB |
Output is correct |
15 |
Correct |
12 ms |
11520 KB |
Output is correct |
16 |
Correct |
11 ms |
11520 KB |
Output is correct |
17 |
Correct |
10 ms |
11520 KB |
Output is correct |
18 |
Correct |
10 ms |
11520 KB |
Output is correct |
19 |
Correct |
10 ms |
11520 KB |
Output is correct |
20 |
Correct |
11 ms |
11520 KB |
Output is correct |
21 |
Correct |
10 ms |
11520 KB |
Output is correct |
22 |
Correct |
9 ms |
11520 KB |
Output is correct |
23 |
Correct |
9 ms |
11520 KB |
Output is correct |
24 |
Correct |
10 ms |
11520 KB |
Output is correct |
25 |
Correct |
11 ms |
11520 KB |
Output is correct |
26 |
Correct |
11 ms |
11648 KB |
Output is correct |
27 |
Correct |
12 ms |
11520 KB |
Output is correct |
28 |
Correct |
10 ms |
11520 KB |
Output is correct |
29 |
Correct |
10 ms |
11520 KB |
Output is correct |
30 |
Correct |
10 ms |
11520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
733 ms |
33144 KB |
Output is correct |
2 |
Correct |
229 ms |
36856 KB |
Output is correct |
3 |
Correct |
710 ms |
36472 KB |
Output is correct |
4 |
Correct |
231 ms |
36856 KB |
Output is correct |
5 |
Correct |
2617 ms |
35832 KB |
Output is correct |
6 |
Correct |
482 ms |
36984 KB |
Output is correct |
7 |
Execution timed out |
3060 ms |
36840 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11392 KB |
Output is correct |
2 |
Correct |
6 ms |
11392 KB |
Output is correct |
3 |
Correct |
7 ms |
11264 KB |
Output is correct |
4 |
Correct |
6 ms |
11392 KB |
Output is correct |
5 |
Correct |
6 ms |
11264 KB |
Output is correct |
6 |
Correct |
6 ms |
11392 KB |
Output is correct |
7 |
Correct |
7 ms |
11264 KB |
Output is correct |
8 |
Correct |
7 ms |
11264 KB |
Output is correct |
9 |
Correct |
7 ms |
11264 KB |
Output is correct |
10 |
Correct |
7 ms |
11264 KB |
Output is correct |
11 |
Correct |
17 ms |
11520 KB |
Output is correct |
12 |
Correct |
12 ms |
11520 KB |
Output is correct |
13 |
Correct |
11 ms |
11520 KB |
Output is correct |
14 |
Correct |
12 ms |
11520 KB |
Output is correct |
15 |
Correct |
12 ms |
11520 KB |
Output is correct |
16 |
Correct |
11 ms |
11520 KB |
Output is correct |
17 |
Correct |
10 ms |
11520 KB |
Output is correct |
18 |
Correct |
10 ms |
11520 KB |
Output is correct |
19 |
Correct |
10 ms |
11520 KB |
Output is correct |
20 |
Correct |
11 ms |
11520 KB |
Output is correct |
21 |
Correct |
10 ms |
11520 KB |
Output is correct |
22 |
Correct |
9 ms |
11520 KB |
Output is correct |
23 |
Correct |
9 ms |
11520 KB |
Output is correct |
24 |
Correct |
10 ms |
11520 KB |
Output is correct |
25 |
Correct |
11 ms |
11520 KB |
Output is correct |
26 |
Correct |
11 ms |
11648 KB |
Output is correct |
27 |
Correct |
12 ms |
11520 KB |
Output is correct |
28 |
Correct |
10 ms |
11520 KB |
Output is correct |
29 |
Correct |
10 ms |
11520 KB |
Output is correct |
30 |
Correct |
10 ms |
11520 KB |
Output is correct |
31 |
Correct |
733 ms |
33144 KB |
Output is correct |
32 |
Correct |
229 ms |
36856 KB |
Output is correct |
33 |
Correct |
710 ms |
36472 KB |
Output is correct |
34 |
Correct |
231 ms |
36856 KB |
Output is correct |
35 |
Correct |
2617 ms |
35832 KB |
Output is correct |
36 |
Correct |
482 ms |
36984 KB |
Output is correct |
37 |
Execution timed out |
3060 ms |
36840 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |