oj.uz

Submission #570803

# Submission time Handle Problem Language Result Execution time Memory
570803 2022-05-31T10:04:30 Z BackNoob One-Way Streets (CEOI17_oneway) C++14
100 / 100
 292 ms 75020 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 3e5 + 227;
const int inf = 1e9 + 277;
const int mod = 24211007;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
struct DSU{
	int n;
	vector<int> lab;
	DSU(){}
	DSU(int _n) {
		n = _n;
		lab.resize(n + 7, -1);
	}
 
	int root(int u) {return lab[u] < 0 ? u : lab[u] = root(lab[u]);}	
	bool union_root(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(u == v) return false;
		if(lab[u] > lab[v]) swap(lab[u], lab[v]);
		lab[u] += lab[v];
		lab[v] = u;
		return true;
	}
} dsu;
 
 
 
int n;
int m;
vector<pair<int, int>> g[mxN];
vector<pair<int, int>> rg[mxN];
vector<pair<int, int>> adj[mxN];
vector<pair<int, int >> tree[mxN];
int p[mxN][LOG];
int depth[mxN];
int idx[mxN];
int low[mxN];
int num[mxN];
int ans[mxN];
int sub[mxN];
int id[mxN];
bool bridge[mxN];
bool vis[mxN];
bool mark[mxN];
int cur[mxN];
int timer = 0;
map<int, int> mp[mxN];
pair<int, int> edges[mxN];
multiset<int> ms1, ms2;
vector<int> node;
int num1[mxN];
int num2[mxN];

 
void dfs(int u, int par)
{
	vis[u] = true;
	low[u] = num[u] = ++timer;
	for(auto it : adj[u]) {
		int v = it.fi;
		int idx = it.se;
		if(v == par) continue;
		if(num[v] == 0) {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] == num[v] && mp[u][v] == 1) {
				bridge[idx] = true;
			}
		}
		else low[u] = min(low[u], num[v]);
	}
}
 
void dfs_tree(int u, int par)
{
	vis[u] = true;
	id[u] = ++timer;
	sub[u] = 1;
	for(auto it: tree[u]) {
		int v = it.fi;
		if(v == par) continue;
		p[v][0] = u;
		depth[v] = depth[u] + 1;
		for(int j = 1; j < LOG; j++) p[v][j] = p[p[v][j - 1]][j - 1];
		dfs_tree(v, u);
		sub[u] += sub[v];
	}
}

void dfs_tree1(int u, int par)
{
	vis[u] = true;
	node.pb(u);
	for(auto it : tree[u]) {
		int v = it.fi;
		int idx = it.se;
		if(v == par) continue;
		dfs_tree1(v, u);
 		cur[u] += cur[v];
		if(bridge[idx] == true && cur[v] > 0) {
			if(edges[idx].fi == u) {
				ans[idx] = 0;
			}
			else {
				ans[idx] = 1;
			}
		}
	}
 	
 	cur[u] += num1[u];
 	cur[u] -= num2[u];
}
 
void dfs_tree2(int u, int par)
{
	for(auto it : tree[u]) {
		int v = it.fi;
		int idx = it.se;
		if(v == par) continue;
		dfs_tree2(v, u);
 		cur[u] += cur[v];
		if(bridge[idx] == true && cur[v] > 0) {
			if(edges[idx].fi == u) {
				ans[idx] = 1;
			}
			else {
				ans[idx] = 0;
			}
		}
	}
	cur[u] += num2[u];
	cur[u] -= num1[u];
 
}

 
void solve()
{	
	cin >> n >> m;
	dsu = DSU(n);
	for(int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		if(dsu.union_root(u, v) == true) {
			tree[u].pb({v, i});
			tree[v].pb({u, i});
			// cout << u << ' ' << v << endl;
		}
		adj[u].pb({v, i});
		adj[v].pb({u, i});
		mp[u][v]++;
		mp[v][u]++;
		edges[i] = {u, v};
	} 
 	
 	for(int i = 1; i <= n; i++) vis[i] = false;
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++) {
		int u, v;
		cin >> u >> v;
		if(u == v) continue;
		g[u].pb({v, i});
		rg[v].pb({u, i});
		num1[u]++;
		num2[v]++;
	}
 	
 	for(int i = 1; i <= n; i++) {
 		if(!vis[i]) dfs(i, -1);
 	}
 
	for(int i = 1; i <= m; i++) ans[i] = 2;
	
	timer = 0;
	for(int i = 1; i <= n; i++) vis[i] = false;
	for(int j = 1; j <= n; j++) {	
		if(vis[j] == true) continue;
		node.clear();
		dfs_tree1(j, -1);
		for(int i : node) cur[i] = 0;
	 	dfs_tree2(j, -1);
	}

	for(int i = 1; i <= m; i++) {
		if(ans[i] == 0) cout << "L";
		if(ans[i] == 1) cout << "R";
		if(ans[i] == 2) cout << "B";
	}
 
 	cout << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
	
    int tc = 1;
    // cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42548 KB Output is correct
2 Correct 21 ms 42580 KB Output is correct
3 Correct 22 ms 42860 KB Output is correct
4 Correct 23 ms 42836 KB Output is correct
5 Correct 22 ms 42936 KB Output is correct
6 Correct 23 ms 42836 KB Output is correct
7 Correct 23 ms 42836 KB Output is correct
8 Correct 23 ms 42836 KB Output is correct
9 Correct 24 ms 42820 KB Output is correct
10 Correct 25 ms 42828 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42548 KB Output is correct
2 Correct 21 ms 42580 KB Output is correct
3 Correct 22 ms 42860 KB Output is correct
4 Correct 23 ms 42836 KB Output is correct
5 Correct 22 ms 42936 KB Output is correct
6 Correct 23 ms 42836 KB Output is correct
7 Correct 23 ms 42836 KB Output is correct
8 Correct 23 ms 42836 KB Output is correct
9 Correct 24 ms 42820 KB Output is correct
10 Correct 25 ms 42828 KB Output is correct
11 Correct 194 ms 59644 KB Output is correct
12 Correct 187 ms 61504 KB Output is correct
13 Correct 196 ms 63996 KB Output is correct
14 Correct 226 ms 65836 KB Output is correct
15 Correct 259 ms 66040 KB Output is correct
16 Correct 255 ms 63528 KB Output is correct
17 Correct 188 ms 66380 KB Output is correct
18 Correct 258 ms 63920 KB Output is correct
19 Correct 234 ms 68140 KB Output is correct
20 Correct 176 ms 61968 KB Output is correct
21 Correct 139 ms 61128 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42548 KB Output is correct
2 Correct 21 ms 42580 KB Output is correct
3 Correct 22 ms 42860 KB Output is correct
4 Correct 23 ms 42836 KB Output is correct
5 Correct 22 ms 42936 KB Output is correct
6 Correct 23 ms 42836 KB Output is correct
7 Correct 23 ms 42836 KB Output is correct
8 Correct 23 ms 42836 KB Output is correct
9 Correct 24 ms 42820 KB Output is correct
10 Correct 25 ms 42828 KB Output is correct
11 Correct 194 ms 59644 KB Output is correct
12 Correct 187 ms 61504 KB Output is correct
13 Correct 196 ms 63996 KB Output is correct
14 Correct 226 ms 65836 KB Output is correct
15 Correct 259 ms 66040 KB Output is correct
16 Correct 255 ms 63528 KB Output is correct
17 Correct 188 ms 66380 KB Output is correct
18 Correct 258 ms 63920 KB Output is correct
19 Correct 234 ms 68140 KB Output is correct
20 Correct 176 ms 61968 KB Output is correct
21 Correct 139 ms 61128 KB Output is correct
22 Correct 273 ms 70112 KB Output is correct
23 Correct 242 ms 67660 KB Output is correct
24 Correct 292 ms 67792 KB Output is correct
25 Correct 263 ms 75020 KB Output is correct
26 Correct 217 ms 69468 KB Output is correct
27 Correct 217 ms 67752 KB Output is correct
28 Correct 89 ms 48776 KB Output is correct
29 Correct 185 ms 64688 KB Output is correct
30 Correct 184 ms 65040 KB Output is correct
31 Correct 267 ms 65404 KB Output is correct
32 Correct 191 ms 66684 KB Output is correct