| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 359987 |
2021-01-27T11:48:44 Z |
soroush |
Mergers (JOI19_mergers) |
C++14 |
|
357 ms |
72672 KB |
/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , k , c[maxn];
vector < int > adj[maxn] , col[maxn];
int root[maxn];
const int lg = 20;
struct LCA{
int n;
int par[lg+3][maxn] , h[maxn];
void dfs(int v , int p , vector < int > *adj){
for(int u : adj[v]) if(u ^ p)
h[u] = h[v] + 1 , par[0][u] = v , dfs(u , v , adj);
}
void init(int N , vector < int > *adj , int root = 1){
n = N;
dfs(root , 0 , adj);
h[0] = -1;
for(int j = 1 ; j <= lg ; j ++)
for(int i = 1 ; i <= n ; i ++)
par[j][i] = par[j - 1][par[j - 1][i]];
}
int lca(int u , int v){
if(h[u] < h[v])
swap(u , v);
for(int i = lg ; i >= 0 ; i --)
if(h[par[i][u]] >= h[v])
u = par[i][u];
if(u == v)
return(u);
for(int i = lg ; i >= 0 ; i --)
if(par[i][u] ^ par[i][v])
u = par[i][u] , v = par[i][v];
return(par[0][v]);
}
int dist(int u , int v){
return(h[u] + h[v] - 2*h[lca(u , v)]);
}
};
LCA lca;
int par[maxn];
int getpar(int v){
return((!par[v]) ? v : par[v] = getpar(par[v]));
}
void merge(int v , int u){
if((u = getpar(u)) == (v = getpar(v)))
return;
par[u] = v;
}
int up[maxn] , h[maxn];
void dfs(int v , int par = 0){
up[v] = h[v];
for(int u : adj[v]){
if(!h[u])
h[u] = h[v] + 1 , dfs(u , v) , up[v] = min(up[v] , up[u]);
if(h[u] < h[v] and u ^ par)
up[v] = min(up[v] , up[u]);
}
if(up[v] < h[v])
merge(v , par);
}
set < int > ad[maxn];
int32_t main(){
migmig;
cin >> n >> k;
for(int i = 1 ; i < n ; i ++){
int u , v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
for(int i = 1 ; i <= n ; i ++)
cin >> c[i] , col[c[i]].pb(i) , root[c[i]] = i;
lca.init(n , adj);
int ans = 0;
for(int i = 1 ; i <= k ; i ++)
for(int v : col[i])
root[i] = lca.lca(root[i] , v);
for(int i = 1 ; i <= k ; i ++)
for(int v : col[i])
adj[v].pb(root[i]) , adj[root[i]].pb(v);
h[1] = 1;
dfs(1);
for(int i = 1 ; i <= n ; i ++){
for(auto u : adj[i])
if(getpar(i) ^ getpar(u))
ad[getpar(i)].insert(getpar(u)) , ad[getpar(u)].insert(getpar(i));
}
for(int i = 1 ; i <= n ; i ++){
if((int)ad[getpar(i)].size() == 1)ans++;
ad[getpar(i)].clear();
}
cout << ans / 2;
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 2 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 3 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 4 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 5 |
Correct |
33 ms |
47468 KB |
Output is correct |
| 6 |
Correct |
33 ms |
47596 KB |
Output is correct |
| 7 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 8 |
Incorrect |
33 ms |
47596 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 2 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 3 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 4 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 5 |
Correct |
33 ms |
47468 KB |
Output is correct |
| 6 |
Correct |
33 ms |
47596 KB |
Output is correct |
| 7 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 8 |
Incorrect |
33 ms |
47596 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 2 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 3 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 4 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 5 |
Correct |
33 ms |
47468 KB |
Output is correct |
| 6 |
Correct |
33 ms |
47596 KB |
Output is correct |
| 7 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 8 |
Incorrect |
33 ms |
47596 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
357 ms |
72672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 2 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 3 |
Correct |
32 ms |
47596 KB |
Output is correct |
| 4 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 5 |
Correct |
33 ms |
47468 KB |
Output is correct |
| 6 |
Correct |
33 ms |
47596 KB |
Output is correct |
| 7 |
Correct |
32 ms |
47468 KB |
Output is correct |
| 8 |
Incorrect |
33 ms |
47596 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
