Submission #110960

#	Time	Username	Problem	Language	Result	Execution time	Memory
110960		igzi	Mergers (JOI19_mergers)	C++17	100 / 100	1342 ms	102372 KiB

mergers

#include <bits/stdc++.h>
#define maxN 500005
 
using namespace std;
 
vector <int> v,adj[maxN],g[maxN];
long long x,y,i,n,k,c[maxN],l[maxN],d[maxN],s[maxN],a[maxN],cnt[maxN];
bool b[maxN];
 
void dfs(int n,int par){
int i;
v.push_back(c[n]);
l[n]=v.size()-1;
d[n]=v.size()-1;
for(i=0;i<adj[n].size();i++){
    if(adj[n][i]!=par){
        dfs(adj[n][i],n);
        d[n]=d[adj[n][i]];
    }
}
}
 
void dfs1(int n,int par){
long long tmp,i;
if(l[n]==0) tmp=0;
else tmp=s[l[n]-1];
if(par!=-1 && (s[d[n]]-tmp)!=0){
g[n].push_back(par);
g[par].push_back(n);
}
for(i=0;i<adj[n].size();i++){
    if(adj[n][i]!=par){
        dfs1(adj[n][i],n);
    }
}
}
 
void dfs2(int n){
int i;
b[n]=true;
x+=adj[n].size()-g[n].size();
for(i=0;i<g[n].size();i++){
    if(!b[g[n][i]]){
        dfs2(g[n][i]);
    }
}
}
 
int main()
{
    srand(time(NULL));
    std::ios_base::sync_with_stdio(0);
    cin>>n>>k;
    for(i=1;i<n;i++){
        cin>>x>>y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(i=0;i<n;i++){
        cin>>c[i];
        c[i]--;
    }
    dfs(0,-1);
    for(i=0;i<n;i++){
        a[i]=rand()+(rand()<<32);
    }
    for(i=0;i<v.size();i++) cnt[v[i]]++;
    for(i=0;i<v.size();i++){
        if(!b[v[i]]){
            s[i]=cnt[v[i]]*a[v[i]];
            b[v[i]]=true;
        }
        s[i]-=a[v[i]];
    }
    for(i=1;i<n;i++){
        s[i]+=s[i-1];
    }
    dfs1(0,-1);
    for(i=0;i<n;i++) b[i]=false;
    y=0;
    for(i=0;i<n;i++){
        if(!b[i]){
            x=0;
            dfs2(i);
            if(x==1) y++;
        }
    }
    cout<<(y+1)/2<<endl;
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:15:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
         ~^~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs1(int, int)':
mergers.cpp:31:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
         ~^~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs2(int)':
mergers.cpp:42:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<g[n].size();i++){
         ~^~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:67:30: warning: left shift count >= width of type [-Wshift-count-overflow]
         a[i]=rand()+(rand()<<32);
                              ^~
mergers.cpp:69:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<v.size();i++) cnt[v[i]]++;
             ~^~~~~~~~~
mergers.cpp:70:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<v.size();i++){
             ~^~~~~~~~~

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