| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944362 |
2024-03-12T15:50:47 Z |
VinhLuu |
Mergers (JOI19_mergers) |
C++17 |
|
44 ms |
51404 KB |
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 5e5 + 5;
const ll oo = 1e16;
const int mod = 1e9 + 7;
const int base = 23;
int n, k, X[N], Y[N], col[N], a[N], f[N], dp[N], in[N], en[N], demin, b[N];
vector<int> p[N], g[N], vr[N], m;
bool fl[N];
void pre(int u,int v){
dp[u] = ((int)p[u].size() == 1);
in[u] = ++demin;
b[demin] = u;
for(auto j : p[u]){
if(j == v) continue;
pre(j, u);
f[u] += f[j];
dp[u] += dp[j];
}
en[u] = demin;
}
void dfs(int u,int v){
if(dp[u] == f[u] && v != 0){
m.pb(u);
return;
}
for(auto j : p[u]){
if(j == v) continue;
dfs(j, u);
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n >> k;
for(int i = 1; i <= n - 1; i ++){
cin >> X[i] >> Y[i];
p[X[i]].pb(Y[i]);
p[Y[i]].pb(X[i]);
}
int root = 1;
for(int i = 1; i <= n; i ++){
if((int)p[i].size() >= 2) root = i;
int x; cin >> x;
vr[x].pb(i);
col[i] = x;
}
for(int i = 1; i < n; i ++){
if(col[X[i]] == col[Y[i]]){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
}
if(n == 1){
cout << 0;
return 0;
}
if(n == 2){
if(col[1] == col[2]){
cout << 0 << "\n";
}else cout << 1 << "\n";
return 0;
}
in[n + 1] = n + 1;
pre(root, 0);
int ans = 0;
for(int i = 1; i <= k; i ++){
if(vr[i].empty()) continue;
queue<int> q;
q.push(vr[i][0]);
fl[vr[i][0]] = true;
while(!q.empty()){
int u = q.front();
q.pop();
for(auto j : g[u]){
if(fl[j]) continue;
fl[j] = true;
q.push(j);
}
}
bool ff = true;
int mi = n + 1;
for(auto j : vr[i]){
if(!fl[j]){
ff = false;
}
if(in[j] < in[mi]) mi = j;
}
if(!ff) continue;
int cnt = 0;
bool gg = true;
for(auto j : vr[i]){
if((int)p[j].size() == 1) cnt++;
else if((int)g[j].size() == 1) gg = false;
}
if(cnt != dp[mi]){
if(cnt == 0 || mi != root || !gg) continue;
}
ans++;
}
cout << (ans + 1) / 2;
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
45404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
45404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
45404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
51404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
45404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
