Submission #911353

#	Time	Username	Problem	Language	Result	Execution time	Memory
911353		BBart888	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	90 ms	30616 KiB

oneway

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <complex>
#include <array>
#include <iomanip>
#include <bitset>
#define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}



using namespace std;
const int MAXN = 1e5 + 111;
using ll = long long;
const int P = 31;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
using ld = long double;
const ld EPS = 1e-5;
using pii = pair<int, int>;
const int K = 300;


int n, m, p;
vector<int> adj[MAXN];
set<int> adj_scc[MAXN];
int scc_cnt;
stack<int> st;
pair<int, int> edges[MAXN];
int tin[MAXN];
int low[MAXN];
int dist[MAXN];
int val[MAXN];
int timer;
int id[MAXN];

void tarjan(int v, int p)
{
	tin[v] = low[v] = ++timer;
	st.push(v);
	bool multi = false;

	for (auto u : adj[v])
	{
		if (u == p && !multi)
		{
			multi = true;
			continue;
		}
		if (!tin[u])
		{
			tarjan(u, v);
			low[v] = min(low[v], low[u]);
		}
		else
			low[v] = min(low[v], tin[u]);
	}

	if (tin[v] == low[v])
	{
		while (st.top() != v)
		{
			//cout << scc_cnt << " " << st.top() << '\n';
			id[st.top()] = scc_cnt;
			st.pop();
		}
		id[st.top()] = scc_cnt;
		//cout << scc_cnt << " " << st.top() << '\n';
		st.pop();
		scc_cnt++;
	}

}


void dfs(int v, int p)
{
	//cout << v << '\n';
	for (auto u : adj_scc[v])
	{
		if (u == p)
			continue;
		//cout << v << " -> " << u << '\n';
		dist[u] = dist[v] + 1;
		dfs(u, v);
		val[v] += val[u];
	}

}


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

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		edges[i] = { a,b };
	}

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

	for (int i = 0; i < m; i++)
	{
		if (id[edges[i].first] != id[edges[i].second])
		{
			adj_scc[id[edges[i].first]].insert(id[edges[i].second]);
			adj_scc[id[edges[i].second]].insert(id[edges[i].first]);
		}
	}

	cin >> p;

	for (int i = 0; i < p; i++)
	{
		int a, b;
		cin >> a >> b;
		val[id[a]]++;
		val[id[b]]--;
	}

	for (int i = 0; i < scc_cnt; i++)
		if (!dist[i])
			dfs(i, i);

	for (int i = 0; i < m; i++)
	{
		int a = id[edges[i].first];
		int b = id[edges[i].second];
		
		if (a == b)
			cout << "B";
		else
		{
			if (dist[a] > dist[b])
			{
				if (val[a] == 0)
					cout << "B";
				else if (val[a] > 0)
					cout << "R";
				else
					cout << "L";
			}
			else
			{
				if (val[b] == 0)
					cout << "B";
				else if (val[b] > 0)
					cout << "L";
				else
					cout << "R";
			}
		}
	}








	return 0;
}

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