# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
938539 | groshi | Mergers (JOI19_mergers) | C++17 | 964 ms | 204708 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct wi{
vector<int> Q;
int kolor=0;
int zle=0;
int gore=0;
int suma=0;
}*w;
int ile[600000];
map<int,int> mapka[600000];
int wynik=0;
int wszyscy=0;
void dfs(int x,int ojc)
{
mapka[x][w[x].kolor]++;
if(ile[w[x].kolor]==1)
mapka[x].erase(w[x].kolor);
for(int i=0;i<w[x].Q.size();i++)
{
int pom=w[x].Q[i];
if(pom==ojc)
continue;
dfs(pom,x);
if(mapka[pom].size()>mapka[x].size())
swap(mapka[pom],mapka[x]);
for(auto it=mapka[pom].begin();it!=mapka[pom].end();it++)
{
mapka[x][it->first]+=it->second;
if(mapka[x][it->first]==ile[it->first])
mapka[x].erase(it->first);
}
}
if(mapka[x].size()==0 && x!=1)
w[x].zle=1,w[ojc].zle=1;
}
void dfs2(int x,int ojc)
{
w[x].suma+=w[x].zle;
int teraz=0;
for(int i=0;i<w[x].Q.size();i++)
{
int pom=w[x].Q[i];
if(pom==ojc)
continue;
dfs2(pom,x);
w[x].suma+=w[pom].suma;
if(w[pom].suma>=1)
teraz++;
}
//cout<<x<<": "<<w[x].suma<<" "<<wszyscy<<" "<<teraz<<"\n";
if(w[x].suma==1 && w[x].zle==1)
wynik++;
else if(w[x].suma==wszyscy && teraz==1 && w[x].zle==1)
wynik++;
}
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n,k,x,y;
cin>>n>>k;
w=new wi[n+3];
for(int i=1;i<n;i++)
{
cin>>x>>y;
w[x].Q.push_back(y);
w[y].Q.push_back(x);
}
for(int i=1;i<=n;i++)
{
cin>>x;
ile[x]++;
w[i].kolor=x;
}
dfs(1,0);
for(int i=1;i<=n;i++)
wszyscy+=w[i].zle;
dfs2(1,0);
//cout<<wynik<<"\n";
cout<<(wynik+1)/2;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |