Submission #1031902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031902		ten_xd	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	63 ms	17056 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()
 
struct Krawedz
{
	int a,b;
};
 
const int MAXN = 1e5+5, MAXM = 1e5+5;
int n = 0, m = 0, p = 0, a = 0, b = 0, korzen = 0, cnt = -1;
vector<int> krawedzie[MAXN];
Krawedz krawedz_in[MAXM];
int wyn[MAXM];
int ile_parent[MAXN];
int glebokosc[MAXN];
int low[MAXN];
int parent[MAXN];
bool czy_most[MAXN];
int w_jakiej_spojnej[MAXN];
int dp[MAXN];
bool visited[MAXN];
int res[MAXN];
 
inline void DFS(int v, int par)
{
	low[v] = glebokosc[v];
	parent[v] = par;
	for(auto x : krawedzie[v])
	{
		if(x == par) ++ile_parent[v];
		else if(glebokosc[x] == -1)
		{
			glebokosc[x] = glebokosc[v] + 1;
			DFS(x,v);
			low[v] = min(low[v],low[x]);
		}
		else low[v] = min(low[v],glebokosc[x]);
	}
	if(ile_parent[v] > 1) low[v] = min(low[v],glebokosc[v]-1);
	if(v != korzen and low[v] == glebokosc[v]) czy_most[v] = true;
}
 
inline void DFS2(int v)
{
	w_jakiej_spojnej[v] = cnt;
	for(auto x : krawedzie[v]) if(w_jakiej_spojnej[x] == -1) DFS2(x);
}
 
inline void DFS3(int v, int par)
{
	parent[v] = par;
	visited[v] = true;
	for(auto x : krawedzie[v])
	{
		if(visited[x] == false)
		{
			DFS3(x,v);
			dp[v] += dp[x];
		}
	}
	if(par != -1) res[v] = dp[v];
}
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	cin >> n >> m;
	rep(i,m)
	{
		cin >> a >> b;
		krawedz_in[i] = {a,b};
		krawedzie[a].pb(b), krawedzie[b].pb(a);
	}
 
	for(int i = 1; i <= n; ++i) glebokosc[i] = -1;
	for(int i = 1; i <= n; ++i)
	{
		if(glebokosc[i] == -1)
		{
			glebokosc[i] = 0, korzen = i;
			DFS(i,0);
		}
	}
 
	for(int i = 1; i <= n; ++i) krawedzie[i] = vector<int>();
	rep(i,m)
	{
		int a = krawedz_in[i].a, b = krawedz_in[i].b;
		if((czy_most[a] == true and parent[a] == b) or (czy_most[b] == true and parent[b] == a)) continue;
		krawedzie[a].pb(b), krawedzie[b].pb(a);
	}
 
 
	for(int i = 1; i <= n; ++i) w_jakiej_spojnej[i] = -1;
	for(int i = 1; i <= n; ++i)
	{
		if(w_jakiej_spojnej[i] == -1)
		{
			++cnt;
			DFS2(i);
		}
	}
 
	for(int i = 1; i <= n; ++i) krawedzie[i] = vector<int>();
	rep(i,m)
	{
		int a = w_jakiej_spojnej[krawedz_in[i].a], b = w_jakiej_spojnej[krawedz_in[i].b];
		if(a == b) wyn[i] = 2;
		else
		{
			krawedzie[a].pb(b), krawedzie[b].pb(a);
		}
	}
 
	cin >> p;
	rep(i,p)
	{
		cin >> a >> b;
		a = w_jakiej_spojnej[a], b = w_jakiej_spojnej[b];
		++dp[a], --dp[b];
	}
 
	for(int i = 1; i <= n; ++i) if(visited[i] == false) DFS3(i,-1);
 
	rep(i,m)
	{
		int a = w_jakiej_spojnej[krawedz_in[i].a], b = w_jakiej_spojnej[krawedz_in[i].b];
		if(a != b)
		{
			if(parent[a] == b)
			{
				if(res[a] == 0) wyn[i] = 2;
				else if(res[a] > 0) wyn[i] = 0;
				else wyn[i] = 1;
			}
			if(parent[b] == a)
			{
				if(res[b] == 0) wyn[i] = 2;
				else if(res[b] > 0) wyn[i] = 1;
				else wyn[i] = 0;
			}
		}
	}
 
	rep(i,m)
	{
		if(wyn[i] == 0) cout << 'R';
		else if (wyn[i] == 1) cout << 'L';
		else cout << 'B';
	}
	cout << '\n';
 
	return 0;
}

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