Submission #1212083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212083		minhpk	Mergers (JOI19_mergers)	C++20	0 / 100	47 ms	34044 KiB

mergers

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
vector <int> z[1000005];
int type[1000005];
int limit[1000005];
int cur[1000005];

int sta[1000005];
int fin[1000005];
int rev[1000005];
int tour;



int child[1000005];
int big[1000005];

int bag1,bag2;
int max1=0;
void dfs(int i,int par){
    tour++;
    sta[i]=tour;
    rev[tour]=i;

    child[i]=1;
    big[i]=-1;
    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         dfs(p,i);
         child[i]+=child[p];
         if (big[i]==-1 || child[big[i]]<child[p]){
              big[i]=p;
         }
    }

    fin[i]=tour;
}

void dfs1(int i,int par,bool keep){

    for (auto p:z[i]){
         if (p!=par && p!=big[i]){
             dfs1(p,i,0);
         }
    }
    if (big[i]!=-1){
        dfs1(big[i],i,1);
    }

    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         if (p==big[i]){
             continue;
         }
         for (int j=sta[p];j<=fin[p];j++){
              int x=rev[j];
              x=type[x];
              if (cur[x]==0){
                  bag2++;
              }
              cur[x]++;
              if (cur[x]==limit[x]){
                  bag2--;
                  bag1++;
              }
         }
    }
    int x=type[i];
    if (cur[x]==0){
        bag2++;
    }
    cur[x]++;
    if (cur[x]==limit[x]){
        bag2--;
        bag1++;
    }
    if (bag1 && !bag2 && par!=0){
        max1=max(max1,bag1);
    }
  //  cout << i << " " << bag1 << " " << bag2 << "\n";
    if (!keep){
        for (int j=sta[i];j<=fin[i];j++){
              x=rev[j];
              x=type[x];
              if (cur[x]==limit[x]){
                  bag2++;
                  bag1--;
              }
              cur[x]--;
              if (cur[x]==0){
                  bag2--;
              }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    for (int i=1;i<=a;i++){
        cin >> type[i];
        limit[type[i]]++;
    }
    dfs(1,0);

    dfs1(1,0,1);
    cout << max1 << "\n";
    return 0;
}

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