제출 #928610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928610		jojo	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	4 ms	18268 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
vector < int > E[100001], TE[100001];
int n, m, p;
pair < int, int > edges[100001], pairs[100001];
vector < int > order;
int fa[100001], vi[100001], dep[100001], covered[100001], com[100001], C, fa2[100001], dep2[100001], J2[17][100001], JC[17][100001];
void DFS(int p, int f, int d)
{
	vi[p] = 1;
	fa[p] = f;
	dep[p] = d;
	order.push_back(p);
	for (int v : E[p])
		if (!vi[v])
			DFS(v, p, d + 1);
		else if (dep[v] < dep[p])
		{
			covered[p]++;
			covered[v]--;
		}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &edges[i].first, &edges[i].second);
		E[edges[i].first].push_back(edges[i].second);
		E[edges[i].second].push_back(edges[i].first);
	}
	scanf("%d", &p);
	for (int i = 1; i <= p; i++)
		scanf("%d%d", &pairs[i].first, &pairs[i].second);
	DFS(1, 0, 0);
	for (auto it = order.rbegin(); *it != 1; it++)
		covered[fa[*it]] += covered[*it];
	for (int u : order)
		if (u == 1 || covered[u] == 1)
			com[u] = ++C;
		else
			com[u] = com[fa[u]];
	for (int i = 2; i <= n; i++)
		if (com[i] != com[fa[i]])
		{
			fa2[com[i]] = com[fa[i]];
			dep2[com[i]] = dep2[com[fa[i]]] + 1;
		}
	for (int i = 1; i <= C; i++)
		J2[0][i] = fa2[i];
	for (int i = 1; i <= 16; i++)
		for (int j = 1; j <= C; j++)
			J2[i][j] = J2[i - 1][J2[i - 1][j]];
	for (int i = 1; i <= p; i++)
	{
		int u = com[pairs[i].first], v = com[pairs[i].second];
		for (int j = 16; j >= 0; j--)
		{
			if (dep2[u] - dep2[v] >= 1 << j)
			{
				JC[j][u] |= 1;
				u = J2[j][u];
			}
			if (dep2[v] - dep2[u] >= 1 << j)
			{
				JC[j][v] |= 2;
				v = J2[j][v];
			}
		}
		if (u == v)
			continue;
		for (int j = 16; j >= 0; j--)
			if (J2[j][u] != J2[j][v])
			{
				JC[j][u] |= 1;
				u = J2[j][u];
				JC[j][v] |= 2;
				v = J2[j][v];
			}
		JC[0][u] |= 1;
		JC[0][v] |= 2;
	}
	for (int i = 16; i; i--)
		for (int j = 1; j <= C; j++)
			if (JC[i][j])
			{
				JC[i - 1][j] |= JC[i][j];
				JC[i - 1][J2[i - 1][j]] |= JC[i][j];
			}
	for (int i = 1; i <= m; i++)
	{
		int u = com[edges[i].first], v = com[edges[i].second], swapped = 0;
		if (u == v)
			putchar('B');
		else
		{
			if (dep2[u] > dep2[v])
			{
				swap(u, v);
				swapped = 1;
			}
			putchar(JC[0][v] == 0 ? 'B' : ((JC[0][v] == 1) != swapped ? 'L' : 'R'));
		}
	}
	puts("");
}

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

oneway.cpp: In function 'int main()':
oneway.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d%d", &edges[i].first, &edges[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &p);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d%d", &pairs[i].first, &pairs[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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