Submission #12802

#	Time	Username	Problem	Language	Result	Execution time	Memory
12802		woqja125	전선 연결하기 (GA9_wire)	C++14	0 / 100	0 ms	8240 KiB

wire

#include<stdio.h>
#include<set>
int d[600001];
int l[300001];
int ans[300001];
int p[300001], e[300001];
struct R
{
	int s, e, n;
	R(int _s, int _e, int _n):s(_s), e(_e), n(_n){}
};
bool operator<(const R &A, const R &B){return A.s<B.s;}
int root(int x){return p[x]==x?x:p[x]=root(p[x]);}
int uni(int a, int b){a=root(a);b=root(b);return p[b] = a;}
void chk(int a, int b)
{
	a = root(a);
	b = root(b);
	if(e[a] != 0) uni(e[a], b);
	if(e[b] != 0) a = uni(e[b], a);
	e[a] = b = root(b);
	e[b] = a;
}
int main()
{
	int n, i;
	int t;
	scanf("%d", &n);
	for(i=1; i<=n; i++) p[i] = i;
	for(i=1; i<=2*n; i++)
	{
		scanf("%d", d+i);
		l[d[i]] = i;
	}
	std::set<R> S;
	for(i=1; i<=2*n; i++)
	{
		t = l[d[i]];
		if(t == i) continue;
		int s, end;
		s=10000000; end = -1;
		while(!S.empty() && S.begin()->e <= i) S.erase(S.begin());
		auto it = S.begin();
		for(; it != S.end() && it->s <= t; it=S.begin())
		{
			if(s > it->s) s = it->s;
			if(end < it->e) end = it->e;
			chk(d[i], it->n);
			S.erase(S.begin());
		}
		int tmp = root(d[i]);
		if(e[tmp] == tmp)
		{
			printf("IMPOSSIBLE");
			return 0;
		}
		if(end!=-1)
			S.insert(R(s, end, e[d[i]]));
		S.insert(R(t, t, d[i]));
	}
//	for(i=1; i<=n; i++) printf("%d %d\n", p[i], e[i]);
	t = root(1);
	for(i=1; i<=2*n; i++)
	{
		if(root(d[i]) == t) printf("^");
		else
		{
			printf("v");
			chk(d[i], t);
			t = root(t);
		}
	}
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39