Znzryb's Blog
0%

ABC-396-E - Min of Restricted Sum

Posted on Edited on

思路讲解

这道题目的图论建模还是很有启发意义的。

如果你发现两个值要不一样，这个就说明他们属于不同的集合。

如果你发现两个值要一样，这个就说明他们属于相同的集合。

按位分析建图，配合dsu解决问题

https://www.luogu.com.cn/problem/P1330 然后01染色，类似于这道题目

P1330 封锁阳光大学

AC代码

1

心路历程（WA，TLE，MLE……）

还是调了比较久的

从低位到高位写已经相当于反过来了（一般数字都是从高位到低位写），不需要用栈再反一次，可以用队列，相当于没反

1
2
3
4
5
6
7
8
9
10
11
12
13
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

这个主要问题在于实现思路有瑕疵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
// 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

*/

还没有查出来哪里有问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
// 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
*/