Submission #1305288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305288		AksLolCoding	Mergers (JOI19_mergers)	C++17	100 / 100	1006 ms	198368 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=5e5+50;
vector<int>E[N];
int n,K,col[N],Num[N];
int par[N],sajz[N];
bool active[N];int num[N];
map<int,int>mapa[N];
int numbad[N];
int root[N];
void DFS(int u,int p=0){
    int v=0;sajz[u]=1;par[u]=p;
    for(auto i:E[u])if(i!=p){
        DFS(i,u);num[u]+=num[i];
        if(sajz[i]>sajz[v])v=i;
        sajz[u]+=sajz[i];
    }
    root[u]=u;
    if(v>0)root[u]=root[v];
    if(mapa[root[u]][col[u]]==0)numbad[root[u]]++;
    mapa[root[u]][col[u]]++;
    if(mapa[root[u]][col[u]]==Num[col[u]])numbad[root[u]]--;
    for(auto i:E[u])if(i!=p&&i!=v){
        for(auto [x,y]:mapa[root[i]]){
            if(mapa[root[u]][x]==0)numbad[root[u]]++;
            mapa[root[u]][x]+=y;
            if(mapa[root[u]][x]==Num[x])numbad[root[u]]--;
        }
    }
    if(p>0&&numbad[root[u]]==0)active[u]=active[p]=true;
    num[u]+=active[u];
}
int main(){
    scanf("%i%i",&n,&K);
    for(int i=1;i<n;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v),E[v].pb(u);
    }
    for(int i=1;i<=n;i++)scanf("%i",&col[i]),Num[col[i]]++;
    DFS(1);
    int ct=0;
    for(int i=1;i<=n;i++)ct+=active[i];
    int res=0;
    for(int i=1;i<=n;i++)if(active[i]){
        if(num[i]==1)res++;
        else if(num[i]==ct){
            bool moze=true;
            for(auto j:E[i])if(j!=par[i]){
                if(0<num[j]&&num[j]<ct-1) moze=false;
            }
            if(moze) res++;
        }
    }
    res=res+1>>1;
    printf("%i\n",res);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%i%i",&n,&K);
      |     ~~~~~^~~~~~~~~~~~~~
mergers.cpp:41:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~
mergers.cpp:44:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     for(int i=1;i<=n;i++)scanf("%i",&col[i]),Num[col[i]]++;
      |                          ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30