oj.uz

Submission #526903

# Submission time Handle Problem Language Result Execution time Memory
526903 2022-02-16T15:42:25 Z AriaH One-Way Streets (CEOI17_oneway) C++17
100 / 100
 355 ms 63064 KB 
/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, m, H[N], mark[N], Up[N], king[N], Ans[N];

vector < pii > G[N], adj[N];

set < pii > st[N];

void dfs(int v, int last)
{
	Up[v] = H[v];
	mark[v] = 1;
	for(auto [u, id] : G[v])
	{
		///printf("v = %d last = %d u = %d id = %d\n", v, last, u, id);
		if((id ^ 1) == last) continue;
		if(mark[u])
		{
			Up[v] = min(Up[v], H[u]);
		}
		else
		{
			H[u] = H[v] + 1;
			dfs(u, id);
			Up[v] = min(Up[v], Up[u]);
		}
	}
	///printf("v = %d H = %d up = %d\n", v, H[v], Up[v]);
}

void dfs2(int v)
{
	mark[v] = 1;
	for(auto [u, id] : G[v])
	{
		if(mark[u]) continue;
		if(Up[u] > H[v])
		{
			king[u] = u;
		}
		else
		{
			king[u] = king[v];
		}
		dfs2(u);
	}
}

void solve(int v, int last)
{
	for(auto [u, id] : adj[v])
	{
		if((id ^ 1) == last) continue;
		solve(u, id);
		if(SZ(st[u]) > SZ(st[v])) st[v].swap(st[u]);
		for(auto now : st[u])
		{
			if(st[v].count({now.F ^ 1, now.S}))
			{
				st[v].erase({now.F ^ 1, now.S});
			}
			else
			{
				st[v].insert(now);
			}
		}
	}
	int side = (last & 1);
	int fir = 0;
	if(SZ(st[v]) != 0)
	{
		fir = (*st[v].begin()).F;
		Ans[last >> 1] = (1 - fir) ^ side;
	}
}

int main()
{
	fast_io;
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back({b, i << 1});
		G[b].push_back({a, i << 1 | 1});
		Ans[i] = -1;
	}
	vector < int > comp;
	for(int i = 1; i <= n; i ++)
	{
		if(!mark[i])
		{
			dfs(i, 0);
			comp.push_back(i);
		}
	}
	memset(mark, 0, sizeof mark);
	for(int i = 1; i <= n; i ++)
	{
		if(!mark[i])
		{
			king[i] = i;
			dfs2(i);
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		for(auto [u, id] : G[i])
		{
			if(king[u] != king[i])
			{
				adj[king[i]].push_back(Mp(king[u], id));
			}
		}
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i ++)
	{
		int a, b;
		cin >> a >> b;
		if(king[a] == king[b])
		{
			continue;
		}
		st[king[a]].insert({0, i});
		st[king[b]].insert({1, i});
	}
	for(auto node : comp)
	{
		solve(node, 0);
	}
	for(int i = 1 ;i <= m; i ++)
	{
		if(Ans[i] == -1)
		{
			cout << "B";
		}
		else if(Ans[i] == 0)
		{
			cout << "R";
		}
		else
		{
			cout << "L";
		}
	}
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10072 KB Output is correct
2 Correct 5 ms 10060 KB Output is correct
3 Correct 6 ms 10112 KB Output is correct
4 Correct 6 ms 10204 KB Output is correct
5 Correct 6 ms 10188 KB Output is correct
6 Correct 6 ms 10120 KB Output is correct
7 Correct 6 ms 10188 KB Output is correct
8 Correct 6 ms 10188 KB Output is correct
9 Correct 5 ms 10188 KB Output is correct
10 Correct 6 ms 10108 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10072 KB Output is correct
2 Correct 5 ms 10060 KB Output is correct
3 Correct 6 ms 10112 KB Output is correct
4 Correct 6 ms 10204 KB Output is correct
5 Correct 6 ms 10188 KB Output is correct
6 Correct 6 ms 10120 KB Output is correct
7 Correct 6 ms 10188 KB Output is correct
8 Correct 6 ms 10188 KB Output is correct
9 Correct 5 ms 10188 KB Output is correct
10 Correct 6 ms 10108 KB Output is correct
11 Correct 44 ms 15720 KB Output is correct
12 Correct 47 ms 16640 KB Output is correct
13 Correct 47 ms 17792 KB Output is correct
14 Correct 69 ms 19072 KB Output is correct
15 Correct 74 ms 19388 KB Output is correct
16 Correct 78 ms 20292 KB Output is correct
17 Correct 77 ms 23080 KB Output is correct
18 Correct 71 ms 20352 KB Output is correct
19 Correct 96 ms 25156 KB Output is correct
20 Correct 44 ms 16320 KB Output is correct
21 Correct 43 ms 16008 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10072 KB Output is correct
2 Correct 5 ms 10060 KB Output is correct
3 Correct 6 ms 10112 KB Output is correct
4 Correct 6 ms 10204 KB Output is correct
5 Correct 6 ms 10188 KB Output is correct
6 Correct 6 ms 10120 KB Output is correct
7 Correct 6 ms 10188 KB Output is correct
8 Correct 6 ms 10188 KB Output is correct
9 Correct 5 ms 10188 KB Output is correct
10 Correct 6 ms 10108 KB Output is correct
11 Correct 44 ms 15720 KB Output is correct
12 Correct 47 ms 16640 KB Output is correct
13 Correct 47 ms 17792 KB Output is correct
14 Correct 69 ms 19072 KB Output is correct
15 Correct 74 ms 19388 KB Output is correct
16 Correct 78 ms 20292 KB Output is correct
17 Correct 77 ms 23080 KB Output is correct
18 Correct 71 ms 20352 KB Output is correct
19 Correct 96 ms 25156 KB Output is correct
20 Correct 44 ms 16320 KB Output is correct
21 Correct 43 ms 16008 KB Output is correct
22 Correct 274 ms 46056 KB Output is correct
23 Correct 355 ms 60156 KB Output is correct
24 Correct 351 ms 63064 KB Output is correct
25 Correct 259 ms 45920 KB Output is correct
26 Correct 283 ms 45436 KB Output is correct
27 Correct 355 ms 51720 KB Output is correct
28 Correct 31 ms 13764 KB Output is correct
29 Correct 131 ms 26484 KB Output is correct
30 Correct 182 ms 29640 KB Output is correct
31 Correct 86 ms 20968 KB Output is correct
32 Correct 220 ms 32716 KB Output is correct