oj.uz

Submission #563708

# Submission time Handle Problem Language Result Execution time Memory
563708 2022-05-18T03:31:43 Z ngpin04 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 132 ms 19860 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];
vector <int> g[N];

vector <int> s;

int comp[N];
int tin[N];
int tout[N];
int num[N];
int low[N];
int par[N];
int anc[N];
int fr[N];
int to[N];
int n,m,timer,nComp;

bool brd[N];
bool vis[N];

char ans[N];

bool isanc(int u, int p) {
	return tin[p] <= tin[u] && tin[u] <= tout[p];
}

int getpar(int u) {
	return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}

void dfs(int u, int p = -1) {
	num[u] = low[u] = ++timer;
	s.push_back(u);
	for (int i : adj[u]) if (i != p) {
		int v = fr[i] ^ to[i] ^ u;
		if (num[v]) {
			mini(low[u], num[v]);
		} else {
			dfs(v, i);
			mini(low[u], low[v]);
		}
	}
	
	if (num[u] == low[u]) {
		nComp++;
		int v;
		do {
			v = s.back();
			s.pop_back();
			comp[v] = nComp;
		} while (v != u);
	}
}

void solve(int u, int p = -1) {
	tin[u] = ++timer;
	anc[u] = p;
	for (int i : g[u]) if (i != p) {
		int v = fr[i] ^ to[i] ^ u;
		solve(v, i);
	}
	tout[u] = timer;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	freopen("oneway.inp","r",stdin);
	freopen("oneway.out","w",stdout);
	#endif
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> fr[i] >> to[i];
		adj[fr[i]].push_back(i);
		adj[to[i]].push_back(i);
	}
	for (int i = 1; i <= m; i++)
		ans[i] = 'B';
		
	for (int i = 1; i <= n; i++)
		if (!num[i])
			dfs(i);
	
	for (int i = 1; i <= m; i++) {
		fr[i] = comp[fr[i]];
		to[i] = comp[to[i]];
		if (fr[i] == to[i])
			continue;
		g[fr[i]].push_back(i);
		g[to[i]].push_back(i);
	}
		
	for (int i = 1; i <= n; i++)
		par[i] = -1;
		
	timer = 0;
	for (int i = 1; i <= nComp; i++)
		if (!tin[i])
			solve(i);
			
	int q; cin >> q;
	while (q--) {
		int u, v; cin >> u >> v;
		u = comp[u];
		v = comp[v];
		
		for (int i = getpar(u); !isanc(v, i);) {
			int ind = anc[i];
			ans[ind] = (fr[ind] == i) ? 'R' : 'L';
			int j = fr[ind] ^ to[ind] ^ i;
			par[i] = j;
			i = getpar(i);
		}
		
		for (int i = getpar(v); !isanc(u, i);) {
			int ind = anc[i];
			ans[ind] = (fr[ind] == i) ? 'L' : 'R';
			int j = fr[ind] ^ to[ind] ^ i;
			par[i] = j;
			i = getpar(i);
		}
	}
	
	for (int i = 1; i <= m; i++)
		cout << ans[i];
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 33 ms 9168 KB Output is correct
12 Correct 36 ms 10260 KB Output is correct
13 Correct 45 ms 11600 KB Output is correct
14 Correct 65 ms 13448 KB Output is correct
15 Correct 53 ms 13924 KB Output is correct
16 Correct 62 ms 15180 KB Output is correct
17 Correct 59 ms 16700 KB Output is correct
18 Correct 65 ms 15192 KB Output is correct
19 Correct 52 ms 17988 KB Output is correct
20 Correct 40 ms 10312 KB Output is correct
21 Correct 35 ms 9936 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 33 ms 9168 KB Output is correct
12 Correct 36 ms 10260 KB Output is correct
13 Correct 45 ms 11600 KB Output is correct
14 Correct 65 ms 13448 KB Output is correct
15 Correct 53 ms 13924 KB Output is correct
16 Correct 62 ms 15180 KB Output is correct
17 Correct 59 ms 16700 KB Output is correct
18 Correct 65 ms 15192 KB Output is correct
19 Correct 52 ms 17988 KB Output is correct
20 Correct 40 ms 10312 KB Output is correct
21 Correct 35 ms 9936 KB Output is correct
22 Correct 75 ms 16716 KB Output is correct
23 Correct 90 ms 15128 KB Output is correct
24 Correct 132 ms 15184 KB Output is correct
25 Correct 77 ms 19860 KB Output is correct
26 Correct 78 ms 16280 KB Output is correct
27 Correct 78 ms 15308 KB Output is correct
28 Correct 27 ms 7120 KB Output is correct
29 Correct 50 ms 9812 KB Output is correct
30 Correct 49 ms 9928 KB Output is correct
31 Correct 50 ms 10336 KB Output is correct
32 Correct 54 ms 13648 KB Output is correct