Submission #604949

#	Time	Username	Problem	Language	Result	Execution time	Memory
604949		pakhomovee	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	228 ms	38016 KiB

oneway

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>
#include <unordered_set>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O2")
using namespace std;

int timer = 0;
int timer1 = 0;

bool IS_BRIDGE[200000];

void dfs(int v, int p, vector<bool>& used, vector<vector<pair<int, int>>>& g, vector<int>& tin, vector<int>& up)
{
	tin[v] = timer++;
	up[v] = tin[v];
	used[v] = true;
	for (pair<int, int> x : g[v])
	{
		int u = x.first;
		int i = x.second;
		if (!used[u])
		{
			dfs(u, v, used, g, tin, up);
			up[v] = min(up[v], up[u]);
			if (up[u] > tin[v])
			{
				IS_BRIDGE[i] = true;
			}
		}
		else if (u != p)
		{
			up[v] = min(up[v], tin[u]);
		}
	}
}

void dfs1(int v, vector<int>& used, vector<vector<pair<int, int>>>& g, int cnt)
{
	used[v] = cnt;
	for (pair<int, int> x : g[v])
	{
		int u = x.first;
		int i = x.second;
		if (!IS_BRIDGE[i] && !used[u])
		{
			dfs1(u, used, g, cnt);
		}
	}
}

int par[17][100000];
int h[100000];

void dfs2(int v, int p, vector<bool>& used, vector<int>& tin, vector<int>& tout, vector<vector<int>>& g)
{
	used[v] = true;
	par[0][v] = p;
	if (p == v)
		h[v] = 0;
	else
		h[v] = h[p] + 1;
	for (int i = 1; i < 17; ++i)
	{
		par[i][v] = par[i - 1][par[i - 1][v]];
	}
	tin[v] = timer1++;
	for (int u : g[v])
	{
		if (!used[u])
		{
			dfs2(u, p, used, tin, tout, g);
		}
	}
	tout[v] = timer1++;
}

bool ok(int a, int b, vector<int>& tin, vector<int>& tout)
{
	if (tin[a] <= tin[b] && tout[a] >= tout[b]) return true;
	return false;
}

int get_lca(int a, int b, vector<int>& tin, vector<int>& tout)
{
	for (int i = 16; i >= 0; --i)
	{
		if (!ok(par[i][a], b, tin, tout))
		{
			a = par[i][a];
		}
	}
	a = par[0][a];
	return a;
}

void dfs3(int v, vector<bool>& used, vector<vector<int>>& g, vector<int>& lol, int w)
{
	h[v] = w;
	used[v] = true;
	for (int u : g[v])
	{
		if (!used[u])
		{
			dfs3(u, used, g, lol, w + 1);
			lol[v] += lol[u];
		}
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		IS_BRIDGE[i] = false;
	}
	vector<vector<pair<int, int>>> g(n);
	vector<int> ans(m, 0);
	map<pair<int, int>, int> d;
	vector<pair<int, int>> e;
	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;
		--u; --v;
		e.push_back({ u, v });
		if (u > v) swap(u, v);
		if (d.count({ u, v }))
		{
			ans[d[{u, v}]] = -1;
		}
		d[{u, v}] = i;
		g[u].push_back({ v, i });
		g[v].push_back({ u, i });
	}
	vector<bool> used(n, false);
	vector<int> tin(n), up(n);
	for (int i = 0; i < n; ++i)
	{
		if (!used[i])
		{
			dfs(i, -1, used, g, tin, up);
		}
	}
	for (int i = 0; i < m; ++i)
	{
		if (IS_BRIDGE[i] && ans[i] == -1)
		{
			IS_BRIDGE[i] = false;
		}
		if (!IS_BRIDGE[i])
		{
			ans[i] = -1;
		}
		//cout << IS_BRIDGE[i] << ' ';
	}
	vector<vector<int>> g1(n);
	vector<int> used1(n, 0);
	int cnt = 1;
	for (int i = 0; i < n; ++i)
	{
		if (!used1[i])
		{
			dfs1(i, used1, g, cnt++);
		}
	}
	for (int i = 0; i < n; ++i)
	{
		--used1[i];
	}
	g1.resize(cnt - 1);
	for (int i = 0; i < n; ++i)
	{
		for (pair<int, int> x : g[i])
		{
			int u = x.first;
			int j = x.second;
			if (IS_BRIDGE[j])
			{
				g1[used1[i]].push_back(used1[u]);
				g1[used1[u]].push_back(used1[i]);
			}
		}
	}
	vector<bool> used2(cnt, false);
	vector<int> tout(cnt);
	vector<int> lol(cnt, 0);
	tin.resize(cnt);
	for (int i = 0; i < cnt - 1; ++i)
	{
		if (!used2[i])
		{
			dfs2(i, 0, used2, tin, tout, g1);
		}
	}
	int p;
	cin >> p;
	for (int i = 0; i < p; ++i)
	{
		int u, v;
		cin >> u >> v;
		--u; --v;
		u = used1[u];
		v = used1[v];
		lol[u] += -1;
		lol[v] += 1;
	}
	used2.assign(cnt, false);
	for (int i = 0; i < cnt - 1; ++i)
	{
		if (!used2[i])
		{
			dfs3(i, used2, g1, lol, 0);
		}
	}
	for (int i = 0; i < m; ++i)
	{
		int u = e[i].first;
		int v = e[i].second;
		u = used1[u];
		v = used1[v];
		//cout << i << ' ' << u << ' ' << v << ' ' << lol[u] << ' ' << lol[v] << endl;
		if ((h[u] > h[v] && lol[u] != 0) || (h[v] > h[u] && lol[v] != 0))
		{
			if (h[u] > h[v] && lol[u] < 0)
			{
				ans[i] = 1;
			}
			else if (h[u] > h[v] && lol[u] > 0)
			{
				ans[i] = 2;
			}
			else if (h[u] < h[v] && lol[v] < 0)
			{
				ans[i] = 2;
			}
			else if (h[u] < h[v] && lol[v] > 0)
			{
				ans[i] = 1;
			}
		}
		else
		{
			ans[i] = -1;
		}
	}
	for (int i : ans)
	{
		if (i == -1)
		{
			cout << 'B';
		}
		else if (i == 1)
		{
			cout << 'R';
		}
		else
		{
			cout << 'L';
		}
	}
}

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