网络规划设计师2024年考试百度优化师

<47.92.197.167:5283/contest/425/problem/3>

根据 $n$ 奇偶性可以推断答案

合法解只需要在任何一棵生成树上构造即可

贪心肯定要在最大生成树上

然后从前往后看一条未选的边能不能选即可

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else#define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 900010
//#define M
//#define mo
int n, m, i, j, k;
int c[N], ans[N], u, v, mn[N], f[N], cho[N]; 
vector<pair<int, int> >G[N], T; int fa(int x) {if(f[x]==x) return x; return f[x]=fa(f[x]); 
}void dfs1(int x, int fa, int id) {for(auto t : G[x]) {int y=t.fi, i=t.se; if(y==fa) continue; debug("%d -> %d (%d)\n", x, y, i); dfs1(y, x, i); }if(fa && c[x]%2==0) c[x]++, c[fa]++, ans[id]=1; 
}void dfs2(int x, int fa) {for(auto t : G[x]) {int y=t.fi, id=t.se; if(y==fa) continue; mn[y]=id; dfs2(y, x); mn[x]=min(mn[x], mn[y]); }
}int dfs3(int x, int fa, int id) {cho[x]=1e9; if(id!=1e9 && ans[id]==0) cho[x]=id; if(id==mn[x]) {if(ans[id]==1) return 1e9; else cho[x]=id; }for(auto t : G[x]) {int y=t.fi, i=t.se; if(y==fa) continue;  dfs3(y, x, i); debug("# %lld -> %lld\n", x, y); cho[x]=min(cho[x], cho[y]); 
//		if(k!=1e9) break;}if(id<cho[x] && ans[id]==1) return cho[x]=1e9; 
//	debug("%lld : %lld | %d || %d\n", x, flg, id, mn[x]); 
//	if(flg && id<=m) ans[id]^=1; return cho[x]; 
}void dfs4(int x, int fa, int id) {if(cho[x]==1e9) return ; sort(G[x].begin(), G[x].end(), [&] (pair<int, int>x, pair<int, int>y) { return cho[x.fi]<cho[y.fi]; }); for(auto t : G[x]) {int y=t.fi, i=t.se; if(y==fa) continue; dfs4(y, x, i); break; }if(cho[x]!=1e9 && fa)  ans[id]^=1; 
}signed main()
{
//	freopen("lilac.in", "r", stdin);
//	freopen("lilac.out", "w", stdout);#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif
//	T=read();
//	while(T--) {
//
//	}n=read(); m=read(); for(i=1; i<=m; ++i) {u=read()+1; v=read()+1; debug("%d %d\n", u, v); T.pb({u, v}); }for(i=1; i<=n; ++i) f[i]=i; for(i=m-1; i>=0; --i) {auto t=T[i]; u=t.fi; v=t.se; if(fa(u)==fa(v)) { ans[i+1]=1; ++c[u]; ++c[v]; continue; }f[fa(u)]=fa(v); G[u].pb({v, i+1}); G[v].pb({u, i+1}); }for(i=1; i<=m; ++i) debug("%d", ans[i]); debug("\n"); for(i=1; i<=n; ++i) debug("%d ", c[i]); debug("\n"); dfs1(1, 0, 0); if(n%2==0) { for(i=1; i<=m; ++i) printf("%d", ans[i]); return 0; }mn[1]=1e9; dfs2(1, 0); for(i=1; i<=n; ++i) debug("%d ", mn[i]); debug("\n"); for(i=1; i<=m; ++i) debug("%d", ans[i]); debug("\n"); dfs3(1, 0, 1e9); for(i=1; i<=m; ++i) debug("%d ", cho[i]); debug("\n"); dfs4(1, 0, 1e9); for(i=1; i<=m; ++i) printf("%d", ans[i]); return 0;
}