Submission #1135347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135347		StefanSebez	Mergers (JOI19_mergers)	C++20	0 / 100	90 ms	50112 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 col[N],cnum[N];bool was[N];
bool moze;
map<int,int>mapa[N];
int nc,rootind[N],num[N];
void DFS(int u,int parent){
    bool leaf=true;
    int maks=0;
    for(auto i:E[u]){
        if(i==parent) continue;
        DFS(i,u);leaf=false;
        if(mapa[rootind[i]].size()>maks){
            maks=mapa[rootind[i]].size();
            rootind[u]=rootind[i];
        }
    }
    if(leaf){
        mapa[++nc][col[u]]=1;
        if(cnum[col[u]]==1) num[nc]=1;
        rootind[u]=nc;
        if(mapa[rootind[u]].size()==num[rootind[u]]) moze=true;
        return;
    }
    for(auto i:E[u]){
        if(i==parent||rootind[i]==rootind[u]) continue;
        for(auto j:mapa[rootind[i]]){
            mapa[rootind[u]][j.fi]+=j.se;
            if(mapa[rootind[u]][j.fi]==cnum[j.fi]) num[rootind[u]]++;
        }
    }
    if(mapa[rootind[u]].size()==num[rootind[u]]) moze=true;
}
int main(){
    int n,K;scanf("%i%i",&n,&K);
    for(int i=1,u,v;i<n;i++) scanf("%i%i",&u,&v),E[u].pb(v),E[v].pb(u);
    for(int i=1;i<=n;i++) scanf("%i",&col[i]),cnum[col[i]]++;
    DFS(1,0);
    if(moze) printf("1\n");
    else printf("0\n");
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:42:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     int n,K;scanf("%i%i",&n,&K);
      |             ~~~~~^~~~~~~~~~~~~~
mergers.cpp:43:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     for(int i=1,u,v;i<n;i++) scanf("%i%i",&u,&v),E[u].pb(v),E[v].pb(u);
      |                              ~~~~~^~~~~~~~~~~~~~
mergers.cpp:44:32: 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]),cnum[col[i]]++;
      |                           ~~~~~^~~~~~~~~~~~~~

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