| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 555356 |
2022-04-30T15:27:17 Z |
urosk |
Mergers (JOI19_mergers) |
C++14 |
|
0 ms |
0 KB |
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 100005
ll n,k;
ll a[maxn];
ll dp[maxn][2];
ll b[maxn];
ll in[maxn];
ll out[maxn];
vector<ll> g[maxn];
vector<ll> v[maxn];
vector<ll> f[maxn];
ll ti = 1;
ll col = -1;
ll con[maxn];
ll dsu[maxn];
ll pari[maxn];
ll root(ll x){
while(x!=dsu[x]){
dsu[x] = dsu[dsu[x]];
x = dsu[x];
}
return x;
}
void upd(ll x,ll y){
x = root(x); y = root(y);
dsu[x] = y;
}
ll root2(ll x){
while(x!=con[x]){
con[x] = con[con[x]];
x = con[x];
}
return x;
}
void upd2(ll x,ll y){
x = root2(x); y = root2(y);
con[x] = y;
}
void updg(ll x,ll y){
upd2(x,y);
f[x].pb(y);
f[y].pb(x);
}
vector<vector<ll> > cnt;
bitset<maxn> st[maxn];
bitset<maxn> up[maxn];
void dfs(ll u,ll par){
st[u][b[u]] = 1;
pari[u] = par;
for(ll s : g[u]){
if(s==par) continue;
dfs(s,u);
st[u] |= st[s];
}
if(u==par) return;
up[u][b[par]] = 1;
up[u]|=up[par];
for(ll s : g[par]){
if(s==pari[u]) continue;
if(s==u) continue;
up[u]|=st[s];
}
if(up[u].count()+st[u].count()!=k) upd(par,u);
}
ll dis[maxn];
ll getnaj(ll u,ll par){
ll y = u;
for(ll s : f[u]){
if(s==par) continue;
dis[s] = dis[u] + 1;
ll e = getnaj(s,u);
if(dis[e]>dis[y]) y = e;
}
return y;
}
ll sizi = 0;
void brisi(ll u,ll par,ll x,vector<ll> w){
w.pb(u);
if(u==x){
for(ll i = 0;i<sz(w)-1;i++){
upd(w[i],w[i+1]);
}
sizi-=(sz(w)-1);
return;
}
for(ll s : f[u]){
if(s==par) continue;
brisi(s,u,x,w);
}
}
bool vis[maxn];
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> k;
iota(dsu+1,dsu+n+1,1);
for(ll i = 1;i<=n-1;i++){
ll x,y; cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
for(ll i = 1;i<=n;i++) cin >> b[i];
for(ll i = 1;i<=n;i++){
v[b[i]].pb(i);
}
dfs(1,1);
for(ll i = 1;i<=n;i++){
if(vis[root(i)]) continue;
vis[root(i)] = 1;
sizi++;
}
iota(con+1,con+n+1,1);
for(ll i = 1;i<=n;i++){
ll x = root(i);
for(ll j : g[i]){
ll y = root(j);
if(root2(x)==root2(y)) continue;
updg(x,y);
}
}
//for(ll i= 1;i<=n;i++) cerr<<root(i)<< " ";
//cerr<<endl;
ll ans = 0;
while(sizi>1){
/*
here;
for(ll i = 1;i<=n;i++){
if(sz(f[i])==0) continue;
cerr<<"i: "<<i<<endl;
for(ll x : f[i]) cerr<<x<< " ";
cerr<<endl;
}
*/
ll poc = 1;
for(ll i = 1;i<=n;i++) if(sz(f[i])>0) poc = i;
//cerr<<"poc: "<<poc<<endl;
fill(dis,dis+n+1,0);
dis[0] = llinf;
ll x = getnaj(poc,poc);
//cerr<<x<<endl;
fill(dis,dis+n+1,0);
dis[0] = llinf;
ll y = getnaj(x,x);
brisi(x,x,y,{});
//cerr<<y<<endl;
for(ll i = 1;i<=n;i++) f[i].clear();
iota(con+1,con+n+1,1);
for(ll i = 1;i<=n;i++){
ll x = root(i);
for(ll j : g[i]){
ll y = root(j);
if(root2(x)==root2(y)) continue;
updg(x,y);
}
}
ans++;
}
cout<<ans<<endl;
return 0;
}
/*
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4
*/
Compilation message
mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:84:35: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | if(up[u].count()+st[u].count()!=k) upd(par,u);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
mergers.cpp: In function 'int main()':
mergers.cpp:8:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
8 | #define llinf 100000000000000000LL // 10^17
| ^~~~~~~~~~~~~~~~~~~~
mergers.cpp:158:18: note: in expansion of macro 'llinf'
158 | dis[0] = llinf;
| ^~~~~
mergers.cpp:8:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '100000000000000000' to '1569325056' [-Woverflow]
8 | #define llinf 100000000000000000LL // 10^17
| ^~~~~~~~~~~~~~~~~~~~
mergers.cpp:163:18: note: in expansion of macro 'llinf'
163 | dis[0] = llinf;
| ^~~~~
/tmp/ccKzDyPK.o: in function `__tcf_0':
mergers.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccKzDyPK.o
/tmp/ccKzDyPK.o: in function `__tcf_1':
mergers.cpp:(.text+0x59): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/ccKzDyPK.o
/tmp/ccKzDyPK.o: in function `__tcf_2':
mergers.cpp:(.text+0xa9): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccKzDyPK.o
/tmp/ccKzDyPK.o: in function `root(int)':
mergers.cpp:(.text+0xfa): relocation truncated to fit: R_X86_64_PC32 against symbol `dsu' defined in .bss section in /tmp/ccKzDyPK.o
/tmp/ccKzDyPK.o: in function `upd(int, int)':
mergers.cpp:(.text+0x137): relocation truncated to fit: R_X86_64_PC32 against symbol `dsu' defined in .bss section in /tmp/ccKzDyPK.o
/tmp/ccKzDyPK.o: in function `root2(int)':
mergers.cpp:(.text+0x1aa): relocation truncated to fit: R_X86_64_PC32 against symbol `con' defined in .bss section in /tmp/ccKzDyPK.o
/tmp/ccKzDyPK.o: in function `upd2(int, int)':
mergers.cpp:(.text+0x1e7): relocation truncated to fit: R_X86_64_PC32 against symbol `con' defined in .bss section in /tmp/ccKzDyPK.o
/tmp/ccKzDyPK.o: in function `dfs(int, int)':
mergers.cpp:(.text+0x260): relocation truncated to fit: R_X86_64_PC32 against symbol `b' defined in .bss section in /tmp/ccKzDyPK.o
mergers.cpp:(.text+0x27a): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccKzDyPK.o
mergers.cpp:(.text+0x2ab): relocation truncated to fit: R_X86_64_PC32 against symbol `pari' defined in .bss section in /tmp/ccKzDyPK.o
mergers.cpp:(.text+0x33b): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
