题目/题解戳这里

这道题题目保证a,b,ca,b,ca,b,c各是一个排列…mdzz考场上想到正解但是没看到是排列,相等的情况想了半天…然后写了暴力60分走人…

由于两两间关系一定,那么就是一个竞赛图(完全图让每一条边都有向).显然就是tarjan.然后发现有很多边其实可以不存在,比如a>b>ca>b>ca>b>c,在竞赛图中就存在3条边a→b,b→c,a→ca\to b,b\to c,a\to ca→b,b→c,a→c.其实最后这一条边已经没有必要连了.那么就可以用主席树优化建边(类似BZOJ 3218 A+B problem(主席树优化网络流建图)).

CODE

选手自带常数巨大…(本地测开了O2O_2O2​还要跑2s+2s+2s+)

#include <cctype>

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

using namespace std;

inline void read(int &num) {

	char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch == '-')flg = -flg;

	for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar()); num*=flg;

}

const int MAXN = 100005;

const int N = 100005 * 20 * 3;

int X, Y, n, m, pos[MAXN];

struct node{ int v[3], id; }p[MAXN];

int in[N], scc[N], dfn[N], stk[N], indx, tmr, scccnt;

vector<int>e[N], g[N];

inline void adde(int u, int v) { if(u&&v)e[u].push_back(v); }

inline void addg(int u, int v) { if(u&&v)g[u].push_back(v), ++in[v]; }

int tarjan(int u) {

	int lowu = dfn[u] = ++tmr;

	stk[++indx] = u;

	for(int v, i = 0, siz = e[u].size(); i < siz; ++i)

		if(!dfn[v=e[u][i]]) lowu = min(lowu, tarjan(v));

		else if(!scc[v]) lowu = min(lowu, dfn[v]);

	if(lowu == dfn[u]) { ++scccnt;

		do scc[stk[indx]] = scccnt;

		while(stk[indx--] != u);

	}

	return lowu;

}

int ls[N], rs[N];

void ins(int &i, int l, int r, int x, int id) {

	++m; ls[m] = ls[i], rs[m] = rs[i]; adde(m, i); i = m;

	if(l == r) adde(i, id);

	else {

		int mid = (l + r) >> 1;

		if(x <= mid) ins(ls[i], l, mid, x, id), adde(i, ls[i]);

		else ins(rs[i], mid+1, r, x, id), adde(i, rs[i]);

	}

}

void link(int i, int l, int r, int x, int id) {

	if(!i) return;

	if(r <= x) adde(id, i);

	else {

		int mid = (l + r) >> 1;

		link(ls[i], l, mid, x, id);

		if(x > mid) link(rs[i], mid+1, r, x, id);

	}

}

inline void work() {

	for(int i = 1; i <= n; ++i) pos[p[i].v[X]] = i;

	int root = 0;

	for(int i = 1; i <= n; ++i)

		ins(root, 1, n, p[pos[i]].v[Y], pos[i]), link(root, 1, n, p[pos[i]].v[Y], pos[i]);

}

bool flag[N]; int ans;

void topo(int u) {

	if(ans) return;

	if(flag[u]) { ans = u; return; }

	for(int i = 0, siz = g[u].size(); i < siz; ++i)

		if(--in[g[u][i]] == 0) topo(g[u][i]);

}

int main () {

	freopen("san.in", "r", stdin);

	freopen("san.out", "w", stdout);

	read(n); m = n;

	for(int i = 1; i <= n; ++i)

		for(int j = 0; j < 3; ++j)

			read(p[i].v[j]);

	X = 0, Y = 1; work();

	X = 0, Y = 2; work();

	X = 1, Y = 2; work();

	for(int i = 1; i <= m; ++i)

		if(!dfn[i]) tarjan(i);

	for(int i = 1; i <= m; ++i)

		for(int j = 0, siz = e[i].size(); j < siz; ++j)

			if(scc[i] != scc[e[i][j]]) addg(scc[i], scc[e[i][j]]);

	for(int i = 1; i <= n; ++i) flag[scc[i]] = 1;

	for(int i = 1; i <= scccnt; ++i)

		if(!in[i]) topo(i);

	for(int i = 1; i <= n; ++i) puts(scc[i] == ans ? "1" : "0");

	return 0;

}