제출 #79334

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

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 7;
const int infint = (int)1e9;
int visited[MAXN], is[MAXN], dp[MAXN], h[MAXN], n, m, par[MAXN], p[MAXN][20], up[MAXN], down[MAXN];
set< pair<int, int> > D;
pair<int, int> edge[MAXN];
vector<pair<int, int> > adj[MAXN];
vector<int> T[MAXN];
void dfs(int v, int index)
{
	dp[v] = h[v];
	visited[v] = 1;
	for(auto u : adj[v])
	{
		if(!visited[u.first])
		{
			h[u.first] = h[v] + 1;
			dfs(u.first, u.second);
			dp[v] = min(dp[v], dp[u.first]);
		}
		else
		{
			if(index != u.second)
				dp[v] = min(dp[v], h[u.first]);
		}
	}
	if(index != -1)
	{
		if(dp[v] == h[v])
			is[index] = 1;
	}
	return;
}
int get(int u)
{
	return par[u] < 0 ? u : par[u] = get(par[u]);
}
void merge(int u, int v)
{
	if((u = get(u)) == (v = get(v)))
		return;
	if(par[u] > par[v])
		swap(u, v); //par[u] > par[v]
	par[u] += par[v];
	par[v] = u;
}
void add(int u, int v)
{
	T[u].push_back(v);
	T[v].push_back(u);
}
void dfs_pre(int u, int P)
{
	visited[u] = 1, p[u][0] = P;
	for (auto v : T[u])
		if(v != P)
		{
			h[v] = h[u] + 1;
			dfs_pre(v, u);
		}
}
int lca(int u, int v)
{
	if(h[u] > h[v])
		swap(u, v);
	for (int i = 19; i >= 0; i--)
		if(h[v] - (1ll << i) >= h[u])	
			v = p[v][i];
	if(u == v)
		return u;
	for (int i = 19; i >= 0; i--)
		if(p[v][i] != p[u][i] && p[u][i] != -1 && p[v][i] != -1)
			v = p[v][i], u = p[u][i];
	return p[v][0];
}
void dfs_col(int u, int P)
{
	for (auto v : T[u])
		if(v != P)
		{
			dfs_col(v, u);
			down[u] += down[v];
			up[u] += up[v];
		}
	if(down[u])
		D.insert({P, u});
	if(up[u])
		D.insert({u, P});
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> edge[i].first >> edge[i].second;
		adj[edge[i].first].push_back({edge[i].second, i});
		adj[edge[i].second].push_back({edge[i].first, i});
	}
	
	for (int i = 1; i <= n; i++)
		if(!visited[i])
			dfs(i, -1);
	memset(par, -1, sizeof par);
	for (int i = 0; i < m; i++)
		if(!is[i])
			merge(edge[i].first, edge[i].second);
	for (int i = 0; i < m; i++)
		if(get(edge[i].first) != get(edge[i].second))
		{
			int u = get(edge[i].first), v = get(edge[i].second);
			add(u, v);
		}
	memset(visited, 0, sizeof visited);
	memset(h, 0, sizeof h);
	memset(p, -1, sizeof p);
	for (int i = 1; i <= n; i++)
		if(!visited[i])
		{
			add(0, i);
			h[i] = 1;
			dfs_pre(i, 0);
		}
	for (int i = 1; i < 20; i++)
		for (int j = 1; j <= n; j++)
			if(p[j][i - 1] != -1)
				p[j][i] = p[p[j][i - 1]][i - 1];
	//derakht moalefeyae yal hambandesho gereftim.
	int q;
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		int x, y;
		cin >> x >> y;
		x = get(x), y = get(y);
		int c = lca(x, y);
		up[x]++, up[c]--;
		down[y]++, down[c]--;
	}
	dfs_col(0, -1);
	for (int i = 0; i < m; i++)
	{
		int u = get(edge[i].first), v = get(edge[i].second);
		if(u == v)
			cout << 'B';
		else
		if(D.count({u, v}))
			cout << 'R';
		else
		if(D.count({v, u}))
			cout << 'L';
		else
			cout << 'B';
	}
}

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