제출 #103830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103830		luciocf	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	309 ms	32688 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxl = 20;

typedef pair<int, int> pii;

int n, m;

int in[maxn], low[maxn], tt;
int comp[maxn], bcc;

int pai[maxn], nivel[maxn];

int tab[maxn][maxl];

int menor[2][maxn];

int ans[maxn];

bool bridge[maxn], mark_tree[maxn];

pii edge[maxn], edgeP[maxn];

vector<pair<int, pii>> grafo[maxn], tree[maxn];

void find_bridge(int u, int ant)
{
	in[u] = low[u] = ++tt;

	for (auto pp: grafo[u])
	{
		int v = pp.first, e = pp.second.first;

		if (e == ant) continue;

		if (in[v])
		{
			low[u] = min(low[u], in[v]);
			continue;
		}

		find_bridge(v, e);

		if (low[v] > in[u]) bridge[e] = true;

		low[u] = min(low[u], low[v]);
	}
}

void mark(int u, int cc)
{
	comp[u] = cc;
	for (auto v: grafo[u])
	{
		if (comp[v.first] || bridge[v.second.first]) continue;
		mark(v.first, cc);
	}
}

void dfs(int u, int p)
{
	mark_tree[u] = true;
	for (auto pp: tree[u])
	{
		int v = pp.first, e = pp.second.first;
		if (v == p) continue;

		nivel[v] = nivel[u]+1, pai[v] = u;
		edgeP[v] = {e, pp.second.second};

		dfs(v, u);
	}
}

void build(void)
{
	memset(tab, -1, sizeof tab);

	for (int i = 1; i <= n; i++)
		tab[i][0] = pai[i];

	for (int j = 1; j < maxl; j++)
		for (int i = 1; i <= n; i++)
			if (tab[i][j-1] != -1)
				tab[i][j] = tab[tab[i][j-1]][j-1];
}

int lca(int u, int v)
{
	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = maxl-1; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			u = tab[u][i];

	if (u == v) return u;

	for (int i = maxl-1; i >= 0; i--)
		if (tab[u][i] != -1 && tab[v][i] != -1 && tab[u][i] != tab[v][i])
			u = tab[u][i], v = tab[v][i];

	return pai[u];
}

int solve1(int u, int p)
{
	int m = 1e9+10;
	mark_tree[u] = true;

	for (auto pp: tree[u])
	{
		int v = pp.first, e = pp.second.first;
		int direct = pp.second.second;

		if (v == p) continue;

		int x = solve1(v, u);

		if (x <= nivel[u])
		{
			if (direct) ans[e] = 0;
			else ans[e] = 1;
		}

		m = min(m, x);
	}

	return min(m, menor[1][u]);
}

int solve0(int u, int p)
{
	int m = 1e9+10;
	mark_tree[u] = true;

	for (auto pp: tree[u])
	{
		int v = pp.first, e = pp.second.first;
		int direct = pp.second.second;

		if (v == p) continue;

		int x = solve0(v, u);

		if (x <= nivel[u])
		{
			if (direct) ans[e] = 1;
			else ans[e] = 0;
		}

		m = min(m, x);
	}

	return min(m, menor[0][u]);
}

int main(void)
{
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		edge[i] = {u, v};

		if (u != v)
		{
			grafo[u].push_back({v, {i, 1}});
			grafo[v].push_back({u, {i, 0}});
		}

		ans[i] = 2;
	}

	for (int i = 1; i <= n; i++)
		if (!in[i])
			find_bridge(i, 0);

	for (int i = 1; i <= n; i++)
		if (!comp[i])
			mark(i, ++bcc);

	for (int i = 1; i <= n; i++)
	{
		for (auto pp: grafo[i])
		{
			int v = pp.first, e = pp.second.first;
			int direct = pp.second.second;

			if (bridge[e]) tree[comp[i]].push_back({comp[v], {e, direct}});
		}
	}

	for (int i = 1; i <= bcc; i++)
	{
		menor[0][i] = menor[1][i] = 1e9+10;
		if (!mark_tree[i])
			dfs(i, 0);
	}

	build();

	int p;
	scanf("%d", &p);

	for (int i = 1; i <= p; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);
		u = comp[u], v = comp[v];
		
		int low = lca(u, v);

		menor[1][u] = min(menor[1][u], nivel[low]);
		menor[0][v] = min(menor[0][v], nivel[low]);
	}

	memset(mark_tree, 0, sizeof mark_tree);
	for (int i = 1; i <= bcc; i++)
		if (!mark_tree[i])
			solve1(i, 0);

	memset(mark_tree, 0, sizeof mark_tree);
	for (int i = 1; i <= bcc; i++)
		if (!mark_tree[i])
			solve0(i, 0);

	for (int i = 1; i <= m; i++)
	{
		if (ans[i] == 2) printf("B");
		else if (ans[i] == 1) printf("R");
		else printf("L");
	}

	printf("\n");
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int main()':
oneway.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:209:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &p);
  ~~~~~^~~~~~~~~~
oneway.cpp:214:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40