TLE on #8 求调,玄关
查看原帖
TLE on #8 求调,玄关
700558
williamwei楼主2024/12/19 14:05
#include <iostream>
using namespace std;
const int maxn = 4e5 + 10;
int n, tot, h[maxn], deg[maxn], used[maxn];
struct Edge {
	int to, nxt;
} e[maxn << 2];
void addedge(int u, int v) {
	e[tot] = {v, h[u]}; h[u] = tot++;
}
void dfs(int u) {
	for (int &k = h[u]; ~k; k = e[k].nxt) 
		if (!used[k >> 1]) used[k >> 1] = 1 + (u <= n), dfs(e[k].to);
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i <= n << 1; i++) h[i] = -1;
	for (int i = 1; i <= n; i++) {
		int u, v; cin >> u >> v;
		addedge(u, v + n); addedge(v + n, u);
		++deg[u]; ++deg[v + n];
	}
	for (int i = 1; i <= n << 1; i++)
		if (deg[i] & 1) addedge(i, 0), addedge(0, i);
	for (int i = 1; i <= n; i++) dfs(i);
	for (int i = 1; i <= n; i++) cout << (used[i - 1] == 1 ? 'b' : 'r');
	return 0;
}
2024/12/19 14:05
加载中...