ABC-396-E - Min of Restricted Sum · znzryb
## 思路讲解
这道题目的图论建模还是很有启发意义的。
如果你发现两个值要不一样，这个就说明他们属于不同的集合。
如果你发现两个值要一样，这个就说明他们属于相同的集合。
按位分析建图，配合dsu解决问题
[https://www.luogu.com.cn/problem/P1330](https://www.luogu.com.cn/problem/P1330) 然后01染色，类似于这道题目
P1330 封锁阳光大学
## AC代码
```cpp
```
## 心路历程（WA，TLE，MLE……）
还是调了比较久的
从低位到高位写已经相当于反过来了（一般数字都是从高位到低位写），不需要用栈再反一次，可以用队列，相当于没反
```cpp
FOR(i,1,M){
ll z=xyz[i][2];
deque<ll> bits;
while(z){
bits.pb(z%2);
z/=2;
}
ll idx=0;
while(!bits.empty()){
bitZ[i][++idx]=bits.front();
bits.pop_front();
}
}
```
[https://atcoder.jp/contests/abc396/submissions/64227463](https://atcoder.jp/contests/abc396/submissions/64227463)
这个主要问题在于实现思路有瑕疵
```cpp
// Problem: E - Min of Restricted Sum
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
arr xyz[MAXN];
ll bitZ[MAXN][35];
ll fa[MAXN][35];
ll pow2[35];
vector<ll> rootDiff[MAXN][35],diffXY[MAXN][35];
ll rootCnt[MAXN][35];
ll limit=0;
ll ans=0;
bool vis[MAXN][35];
bool needAdd[MAXN][35];
ll find(ll lay,ll x){
if(fa[x][lay]==x) return x;
return fa[x][lay]=find(lay,fa[x][lay]);
}
void merge(ll lay,ll x,ll y){
fa[x][lay]=find(lay,y);
rootCnt[y][lay]+=rootCnt[x][lay];
}
void dfs(ll lay,ll x,ll color,vector<ll> &vis0,vector<ll> &vis1){
if(vis[x][lay]) return;
vis[x][lay]=true;
if(color==1) vis1.pb(x),ans+=rootCnt[x][lay];
else vis0.pb(x);
FOR(i,0,SZ(rootDiff[x][lay])-1){
ll v=rootDiff[x][lay][i];
if(vis[v][lay]) continue;
dfs(lay,v,1-color,vis0,vis1);
}
}
inline void solve(){
cin>>N>>M;
FOR(i,1,M){
cin>>xyz[i][0]>>xyz[i][1]>>xyz[i][2];
}
limit=ceil(log(N)/log(2))+1;
FOR(i,1,N){
FOR(j,1,limit){
fa[i][j]=i;
rootCnt[i][j]=1;
}
}
FOR(i,1,M){
ll z=xyz[i][2];
deque<ll> bits;
while(z){
bits.pb(z%2);
z/=2;
}
ll idx=0;
while(!bits.empty()){
bitZ[i][++idx]=bits.front();
bits.pop_front();
}
}
FOR(j,1,limit){
FOR(i,1,M){
ll x=xyz[i][0],y=xyz[i][1];
if(bitZ[i][j]==0){
merge(j,x,y);
}
}
FOR(i,1,M){
ll x=xyz[i][0],y=xyz[i][1];
if(bitZ[i][j]==1){
// 该条件与前面的要求冲突了，直接输出-1
if(find(j,x)==find(j,y) && x!=y){
cout<<-1<<"\n";
return;
}else{
diffXY[x][j].pb(y);
diffXY[y][j].pb(x);
}
}
}
}
#ifdef LOCAL
cerr << "OK1" << '\n';
#endif
FOR(i,1,N){
FOR(j,1,limit){
FOR(k,0,SZ(diffXY[i][j])-1){
ll fai=find(j,i),fax=find(j,diffXY[i][j][k]);
rootDiff[fai][j].pb(fax);
}
}
}
// 去重
FOR(i,1,N){
FOR(j,1,limit){
sort(all(rootDiff[i][j]));
rootDiff[i][j].resize(unique(all(rootDiff[i][j]))-rootDiff[i][j].begin());
}
}
#ifdef LOCAL
cerr << "OK2" << '\n';
FOR(i,1,N){
FOR(j,1,limit){
if(rootDiff[i][j].empty()) continue;
cerr<<i<<": ";
FOR(k,0,SZ(rootDiff[i][j])-1){
cerr<<rootDiff[i][j][k]<<" ";
}
cerr<<"\n";
}
}
#endif
// 然后对每层01染色就行了
FOR(i,1,limit){
FOR(j,1,N){
ll faj=find(i,j);
if(vis[faj][i]) continue;
vector<ll> vis0,vis1,vis00,vis11;
ans=0;
dfs(i,faj,0,vis0,vis1);
// #ifdef LOCAL
// cerr << "OK--"<< i<<" "<<j << '\n';
// #endif
FOR(k,0,SZ(vis0)-1){
vis[vis0[k]][i]=false;
}
FOR(k,0,SZ(vis1)-1){
vis[vis1[k]][i]=false;
}
ll lans=ans;
ans=0;
dfs(i,faj,1,vis00,vis11);
#ifdef LOCAL
cerr<<"vis11: ";
for(int k=0;k<vis11.size();++k){
cerr<<vis11[k]<<" ";
}
cerr<<"\n";
cerr<<"vis1: ";
for(int k=0;k<vis1.size();++k){
cerr<<vis1[k]<<" ";
}
cerr<<"\n";
#endif
if(lans<ans){
FOR(k,0,SZ(vis1)-1){
needAdd[vis1[k]][i]=true;
}
}else{
FOR(k,0,SZ(vis11)-1){
needAdd[vis11[k]][i]=true;
}
}
}
}
// #ifdef LOCAL
// cerr << "OK3" << '\n';
// #endif
FOR(i,1,limit){
FOR(j,1,N){
ll faj=find(i,j);
if(needAdd[faj][i]){
A[j]+=pow2[i];
}
}
}
FOR(i,1,M){
// 免去我们无向图判偶数环，直接校验我们的答案正确性
ll x=xyz[i][0],y=xyz[i][1],z=xyz[i][2];
if((A[x]^A[y])!=z){
cout<<-1<<"\n";
return;
}
}
FOR(i,1,N){
cout<<A[i]<<" ";
}
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>T;
// while(T--){
// solve();
// }
pow2[1]=1; // 采用的是1-based
FOR(i,2,33){
pow2[i]=pow2[i-1]*2;
}
solve();
return 0;
}
/*
WA https://atcoder.jp/contests/abc396/submissions/64227025
*/
```
还没有查出来哪里有问题
```cpp
// Problem: E - Min of Restricted Sum
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
arr xyz[MAXN];
ll bitZ[MAXN][35];
ll fa[MAXN][35];
ll pow2[35];
vector<ll> rootDiff[MAXN][35],diffXY[MAXN][35];
ll rootCnt[MAXN][35];
ll limit=0;
ll ans=0;
ll sum=0;
ll vis[MAXN][35];
bool needAdd[MAXN][35];
bool abNormal=false;
ll find(ll lay,ll x){
if(fa[x][lay]==x) return x;
return fa[x][lay]=find(lay,fa[x][lay]);
}
void merge(ll lay,ll x,ll y){
ll fax=find(lay,x),fay=find(lay,y);
fa[fax][lay]=fay;
rootCnt[fay][lay]+=rootCnt[fax][lay];
}
void dfs(ll lay,ll x,ll color,vector<ll> &vis0,vector<ll> &vis1){
if(abNormal) return;
if(vis[x][lay]!=0 && vis[x][lay]!=color){
abNormal=true;
return;
}else if(vis[x][lay]!=0){
return;
}
vis[x][lay]=color;
if(color==2) vis1.pb(x),ans+=rootCnt[x][lay],sum+=rootCnt[x][lay];
else vis0.pb(x),sum+=rootCnt[x][lay];
FOR(i,0,SZ(rootDiff[x][lay])-1){
ll v=rootDiff[x][lay][i];
if(vis[v][lay]) continue;
dfs(lay,v,3-color,vis0,vis1);
}
}
inline void solve(){
cin>>N>>M;
FOR(i,1,M){
cin>>xyz[i][0]>>xyz[i][1]>>xyz[i][2];
}
limit=ceil(log(N)/log(2))+1;
FOR(i,1,N){
FOR(j,1,limit){
fa[i][j]=i;
rootCnt[i][j]=1;
}
}
FOR(i,1,M){
ll z=xyz[i][2];
deque<ll> bits;
while(z){
bits.pb(z%2);
z/=2;
}
ll idx=0;
while(!bits.empty()){
bitZ[i][++idx]=bits.front();
bits.pop_front();
}
}
#ifdef LOCAL // bitZ 没有问题
FOR(i,1,M){
cerr<<xyz[i][0]<<" "<<xyz[i][1]<<" "<<xyz[i][2]<<": ";
FOR(lay,1,limit){
cerr<<bitZ[i][lay]<<" ";
}
cerr<<"\n";
}
#endif
FOR(j,1,limit){
FOR(i,1,M){
ll x=xyz[i][0],y=xyz[i][1];
if(bitZ[i][j]==0){
merge(j,x,y);
}
}
FOR(i,1,M){
ll x=xyz[i][0],y=xyz[i][1];
if(bitZ[i][j]==1){
// 该条件与前面的要求冲突了，直接输出-1
if(find(j,x)==find(j,y) && x!=y){
cout<<-1<<"\n";
return;
}else{
diffXY[x][j].pb(y);
diffXY[y][j].pb(x);
}
}
}
}
// #ifdef LOCAL
// cerr << "OK1" << '\n';
// #endif
FOR(i,1,N){
FOR(j,1,limit){
FOR(k,0,SZ(diffXY[i][j])-1){
ll fai=find(j,i),fax=find(j,diffXY[i][j][k]);
rootDiff[fai][j].pb(fax);
}
}
}
// 去重
FOR(i,1,N){
FOR(j,1,limit){
sort(all(rootDiff[i][j]));
rootDiff[i][j].resize(unique(all(rootDiff[i][j]))-rootDiff[i][j].begin());
#ifdef LOCAL
cerr<<"lay: "<<j<<" node:"<<i<<"/ ";
for(int k=0;k<rootDiff[i][j].size();++k){
cerr<<rootDiff[i][j][k]<<" ";
}
cerr<<"\n";
#endif
}
}
// 然后对每层01染色就行了
FOR(i,1,limit){
FOR(j,1,N){
ll faj=find(i,j);
if(vis[faj][i]!=0) continue;
vector<ll> vis0,vis1;
ans=0;
sum=0;
abNormal=false;
dfs(i,faj,1,vis0,vis1);
if(abNormal){
cout<<-1<<"\n";
return;
}
if(ans<sum-ans){
FOR(k,0,SZ(vis1)-1){
needAdd[vis1[k]][i]=true;
}
}else{
FOR(k,0,SZ(vis0)-1){
needAdd[vis0[k]][i]=true;
}
}
}
}
FOR(i,1,limit){
FOR(j,1,N){
ll faj=find(i,j);
if(needAdd[faj][i]){
A[j]+=pow2[i];
}
}
}
FOR(i,1,M){
// 免去我们无向图判偶数环，直接校验我们的答案正确性
ll x=xyz[i][0],y=xyz[i][1],z=xyz[i][2];
if((A[x]^A[y])!=z){
cout<<-1<<"\n";
return;
}
}
FOR(i,1,N){
cout<<A[i]<<" ";
}
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
pow2[1]=1; // 采用的是1-based
FOR(i,2,33){
pow2[i]=pow2[i-1]*2;
}
solve();
return 0;
}
/*
WA https://atcoder.jp/contests/abc396/submissions/64227025
0 8 13 4 0 1 13 0 0 0 2 0 0 0 0
15 6
3 10 13
2 7 5
5 4 4
11 7 15
5 7 13
15 6 1
ans:
0 8 0 4 0 0 13 0 0 13 2 0 0 0 1
*/
```