【Moscow Workshop 2019 WinterCamp day3 divB L】LED-led Paths 题解

题目大意

  给定一幅 $n$ 个点 $m$ 条边的 DAG。你有三种颜色（红蓝绿），你要给每条边染色，使得不存在一条路径上连续 42 条边同色。
  $n \leq 50000,\ m \leq 2 \times 10^5$

naive想法1

  今天的主题是 random algorithm，于是下午的 contest 就变成了随机大战+乱搞大战。于是这题理所当然地首先想想随机。
  似乎直接给每条边随机一个颜色很优秀啊？你想想，一条路径连续 42 个同色的概率不是几乎为 0 吗？
  然而非常好叉，因为这不是随机图，只要让两个点之间重边非常多，那么在随机下每个点到另一个点什么颜色都有了，轻松 42 条同色。
  然后又脑洞了一下：给每个点随机一种颜色然后这个点的出边全都是这种颜色、按 bfs 序每15层全部同色轮换然后其他随机……全都 WA 了。然后发现，只要把点分层，每层 100 个，共 500 层，相邻两层之间完全相连，不同层之间再随便加些边扰动一下，那么在随机下每层到下一层也是什么颜色都有，依然轻松 42 条同色。

  因此本质问题是，上面这种数据就是卡掉所有随机的。思考的方向不是让它如何更随机，因为越随机，这种数据越过不去。应该构造一种方案使得它在这种情况下不那么随机。
  因此这是一个构造题。

naive想法2

  需要构造一种方法，使得如果连续 42 条边同色的话，会有什么东西爆掉。比如让点的编号爆掉。
  有一种很 naive 的想法是，设 $x$ 的二进制最高位的 1 是从右往左数第 $w_x$ 位，比如 $i$ 连向 $j$，若 $i < j$，且 $w_i < w_j$，那么 $i$ 到 $j$ 连红边。这样的话，红边连续意味着二进制最高位的 1 一直向前推进，那么连续 42 次编号肯定爆了。然后比如当 $w_i > w_j$ 时连绿边，那么连续 42 条绿边也爆了……

  但是还有很多情况没考虑，比如 $w_i=w_j$ 怎么连……会发现三种颜色不太够，因此方法要改进一下。

  基于这种思路就得出了一种构造方法。
  首先为了去掉 $i > j$ 的情况，我们用拓扑序编号来做。对于 $i$ 连向 $j$，设它们的拓扑序编号分别为 $id_i$ 和 $id_j$，那么一定有 $id_i < id_j$。
  然后我们不要讨论最高位的 1，而是讨论 $id_i$ 和 $id_j$ 二进制下第一个不同的位，即 $w_{id_i \oplus id_j}$。由于 $n \leq 50000$，因此 $id$ 二进制最多只有 16 位，那么我们对 $w_{id_i \oplus id_j}$ 进行讨论：若为 $1$~$5$，连红边；若为 $6$~$10$，连绿边；若为 $11$~$16$，连蓝边。这样红边和绿边的连续转移都不超过 $2^5=32$ 次。蓝边因为有第 16 位，严格分析一下最大是 $48$ 次。

  比赛时脑子抽了以为蓝边也是 32 次，于是勇敢地写了，然后过了。。。
  估计出题人也没想过我这种偏门的想法于是没有专门出数据去卡。。。
  直到写这个 blog 重新证明一次才发现被叉掉了 qaq
  不过这场本身也是乱搞大战，我乱搞过了这个题不也算是正解吗（大雾

  （当然还是希望有 dalao 继续完善一下这个想法。

题解

  然后题解异常地简单，思路很直接。（其实是因为我想的太复杂了qaq

  先对点进行分组，分成 $42$ 个组，每组 $\frac{n}{42}$ 个点。组与组之间的转移连红边。由于是 DAG，红边连续最多 41 次。
  对于每组内，再分 $42$ 个小组，每小组 $\frac{n}{42 \cdot 42}$ 个点。小组与小组之间转移连蓝边。同理，蓝边连续最多 41 次。
  由于小组内点数 $\frac{n}{42 \cdot 42} < 42$，因此小组内转移连绿边。这样绿边连续也不超过 42 次了。

  这个方法用的思想是 $42^3>n$，因此连续分组两次就行了。

代码

// naive想法2

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=5e4+5, maxm=2e5+5;

int n,m;
char clr[3]={'R','B','G'};

int tot,go[maxm],fro[maxm],nxt[maxm],f1[maxn],com[maxn];
void ins(int x,int y)
{
	go[++tot]=y;
	fro[tot]=x;
	nxt[tot]=f1[x];
	f1[x]=tot;
	com[y]++;
}

int d[maxn],dis[maxn];
void topo()
{
	int j=0;
	fo(i,1,n) if (!com[i])
	{
		d[++j]=i;
		dis[i]=1;
	}
	for(int i=1; i<=j; i++)
	{
		for(int p=f1[d[i]]; p; p=nxt[p])
		{
			dis[go[p]]=max(dis[go[p]],dis[d[i]]+1);
			if (--com[go[p]]==0) d[++j]=go[p];
		}
	}
}

int main()
{
	srand(time(0));
	
	scanf("%d %d",&n,&m);
	fo(i,1,m)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		ins(x,y);
	}
	
	topo();
	
	fo(i,1,m)
	{
		int w=0;
		for(int x=dis[fro[i]]^dis[go[i]]; x; x>>=1, w++);
		printf("%c\n",clr[w%3]);
	}
}