Submission #44553

#	Time	Username	Problem	Language	Result	Execution time	Memory
44553		MatheusLealV	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	433 ms	62668 KiB

oneway

#include <bits/stdc++.h>
#define N 100050
#define logn 20
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int q, n, m, dfsnum[N], dfslow[N], cnt, pai[N];

int anc[N][logn], used[N], nivel[N], dp[N], ans[N];

int solved[N];

vector<int> pontes;

map<pii, int> ccnt;

vector<pii> G[N], A, grafo[N];

void dfs(int x)
{
	dfsnum[x] = dfslow[x] = ++cnt;

	for(int i = 0; i< G[x].size(); i++)
	{
		int v = G[x][i].f, id = G[x][i].s;

		if(!dfsnum[v])
		{
			pai[v] = x;

			dfs(v);

			if(dfslow[v] > dfsnum[x] && ccnt[{ min(x, v), max(x, v) }] == 1 ) pontes.push_back(id);

			dfslow[x] = min(dfslow[v], dfslow[x]);
		}

		else if(v != pai[x]) dfslow[x] = min(dfsnum[v], dfslow[x]);
	}
}

int ok[N], esq[N], dir[N];

vector<pii> tree[N];

void get_tree(int x)
{
	ok[x] = 1;

	for(auto v: G[x])
	{
		if(ok[v.f]) continue;
		
		tree[x].push_back(v);

		tree[v.f].push_back({x, v.s});

		get_tree(v.f);
	}
}

int solve(int x, int p)
{
	for(auto v: tree[x])
	{
		if(v.f == p) continue;
		
		int child = solve(v.f, x);

		bool brg = binary_search(pontes.begin(), pontes.end(), v.s);

		if(child > 0 && brg)
		{
			if(esq[v.s] == x) ans[v.s] = -1;

			else ans[v.s] = 1;
		}

		else if(child < 0 && brg)
		{
			if(esq[v.s] == x) ans[v.s] = 1;

			else ans[v.s] = -1;
		}

		dp[x] += child;
	}

	solved[x] = 1;

	return dp[x];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1, a, b ;i <= m; i++)
	{
		cin>>a>>b;

		G[a].push_back({b, i - 1});

		G[b].push_back({a, i - 1});

		A.push_back({a, b});

		esq[i - 1] = a, dir[i - 1] = b;

		ccnt[ {min(a, b), max(a, b)}] ++;
	}

	for(int i = 1; i <= n; i++) if(!dfsnum[i]) dfs(i);

	for(auto id: pontes) grafo[ A[id].f ].push_back( {A[id].s, id} ), grafo[ A[id].s ].push_back( {A[id].f, id} );

	cin>>q;

	for(int i = 1, a, b; i <= q; i++)
	{
		cin>>a>>b;

		dp[a] ++, dp[b] --;
	}

	sort(pontes.begin(), pontes.end());

	for(int i = 1; i <= n; i++)
	{
		if(ok[i] == 0) get_tree(i);
	}

	for(int i = 1; i <= n; i++) if(!solved[i]) solve(i, i);

	for(int i = 0; i < m; i++)
	{
		if(ans[i] == 0) cout<<"B";

		else if(ans[i] > 0) cout<<"R";

		else cout<<"L";
	}

	cout<<"\n";
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int)':
oneway.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< G[x].size(); i++)
                 ~^~~~~~~~~~~~~

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