Submission #938539

#TimeUsernameProblemLanguageResultExecution timeMemory
938539groshiMergers (JOI19_mergers)C++17
100 / 100
964 ms204708 KiB
#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)

mergers.cpp: In function 'void dfs(long long int, long long int)':
mergers.cpp:20:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<w[x].Q.size();i++)
      |                 ~^~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs2(long long int, long long int)':
mergers.cpp:42:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<w[x].Q.size();i++)
      |                 ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...