| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 716265 |
2023-03-29T12:24:26 Z |
Ahmed57 |
Mergers (JOI19_mergers) |
C++14 |
|
107 ms |
71048 KB |
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 5e5+5;
int n, k;
vector<int> g[N];
vector<pii> E;
int dep[N], dsu[N], deg[N], par[N];
vector<int> col[N];
int find(int u) { return dsu[u] = dsu[u] == u ? u : find(dsu[u]); }
void init_dep(int u, int p) {
dep[u] = dep[p] + 1, par[u] = p;
for(int v : g[u]) if(v != p) init_dep(v, u);
}
int arr[200001] , cnt[200001];
bool mark[200001];
pair<int,map<int,int>> dfs(int i,int pr){
map<int,int> mp;
pair<int,map<int,int>> p1;
int bad = 0;
mp[arr[i]]++;
if(cnt[arr[i]]!=1)bad++;
for(auto j:g[i]){
if(j!=pr){
p1 = dfs(j,i);
bad+=p1.first;
if(p1.second.size()>mp.size())swap(mp,p1.second);
for(auto k:p1.second){
if(mp[k.first]!=0)bad--;
mp[k.first]+=k.second;
if(mp[k.first]==cnt[k.first]&&k.second!=cnt[k.first])bad--;
}
}
}
if(bad==0){
mark[i] = 1;
}
return {bad,mp};
}
int calc(int i,int pr){
int sum = 0;
for(auto j:g[i]){
if(j==pr)continue;
sum+=calc(j,i);
}
if(mark[i]){
if(sum)return sum;
else return 1;
}else return sum;
}
int main() {
iota(dsu, dsu+N, 0);
scanf("%d %d", &n, &k);
for(int i = 1, u, v; i < n; ++i) {
scanf("%d %d", &u, &v);
g[u].emplace_back(v), g[v].emplace_back(u);
E.emplace_back(u, v);
}
for(int i = 1, v; i <= n; ++i) {
scanf("%d", &v);
arr[i] = v;
cnt[v]++;
col[v].emplace_back(i);
}
init_dep(1, 0);
for(int i = 1; i <= k; ++i) if(col[i].size() > 1) {
for(int j = 1; j < col[i].size(); ++j) {
int a = find(col[i][j-1]), b = find(col[i][j]);
while(a != b) {
if(dep[a] < dep[b]) swap(a, b);
dsu[a] = find(par[a]);
a = dsu[a];
}
}
}
for(auto x : E) {
int a = find(x.x), b = find(x.y);
if(a != b) deg[a]++, deg[b]++;
}
int cnt = 0;
for(int i = 1; i <= n; ++i) if(deg[i] == 1) cnt++;
pair<int,map<int,int>>p1;
int ans = calc(1,0);
if((ans+1)/2<(cnt+1)/2)assert(0);
printf("%d\n", (cnt+1) / 2);
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int j = 1; j < col[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~
mergers.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d", &v);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
52104 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
52104 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
52104 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
31824 KB |
Output is correct |
| 2 |
Runtime error |
107 ms |
71048 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
52104 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
