oj.uz

Submission #51196

# Submission time Handle Problem Language Result Execution time Memory
51196 2018-06-17T07:55:12 Z adamczh1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 806 ms 89540 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int n, m, p;
vector<int> adj[MAXN];
int a[MAXN], b[MAXN];
int x[MAXN], y[MAXN];

map<pair<int, int>, int> cnt;

int Time;
int dfn[MAXN], low[MAXN];
map<pair<int, int>, bool> bridge;

void dfs(int cur, int p = -1) {
	dfn[cur] = low[cur] = ++Time;
	for (int v : adj[cur]) if (v != p) {
		if (!dfn[v]) {
			dfs(v, cur);
			low[cur] = min(low[cur], low[v]);
			if (low[v] > dfn[cur] && cnt[make_pair(cur, v)] == 1) {
				bridge[make_pair(cur, v)] = bridge[make_pair(v, cur)] = true;
			}
		} else if (dfn[v] < dfn[cur]) {
			low[cur] = min(low[cur], dfn[v]);
		}
	}
}

bitset<MAXN> vis;
int n_blocks;
int block[MAXN];

void dfs2(int cur, int p = -1) {
	vis[cur] = 1;
	if (p != -1) {
		block[cur] = block[p];
	}
	for (int v : adj[cur]) if (v != p) {
		if (!vis[v] && !bridge[make_pair(cur, v)]) {
			dfs2(v, cur);
		}
	}
}

set<int> tadj[MAXN];

int pre[MAXN];
map<pair<int, int>, char> mp;

int dfs3(int cur, int p = -1) {
	vis[cur] = 1;
	int val = pre[cur];
	for (int v : tadj[cur]) if (v != p) {
		val += dfs3(v, cur);
	}
	pair<int, int> pi = make_pair(p, cur);
	pair<int, int> rv = make_pair(cur, p);
	if (val < 0) {
		mp[pi] = 'L';
		mp[rv] = 'R';
	} else if (val > 0) {
		mp[pi] = 'R';
		mp[rv] = 'L';
	} else {
		mp[pi] = mp[rv] = 'B';
	}
	return val;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i];
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
		cnt[make_pair(a[i], b[i])]++;
		cnt[make_pair(b[i], a[i])]++;
	}
	cin >> p;
	for (int i = 1; i <= p; i++) {
		cin >> x[i] >> y[i];
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			dfs(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			block[i] = ++n_blocks;
			dfs2(i);
		}
	}
	for (int i = 1; i <= m; i++) {
		int A = block[a[i]];
		int B = block[b[i]];
		if (A != B) { // bridge
			tadj[A].insert(B);
			tadj[B].insert(A);
		}
	}
	for (int i = 1; i <= p; i++) {
		int u = block[x[i]];
		int v = block[y[i]];
		if (u == v) {
			continue;
		}
		pre[u]--;
		pre[v]++;
	}
	vis.reset();
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs3(i);
		}
	}
	for (int i = 1; i <= m; i++) {
		int u = block[a[i]];
		int v = block[b[i]];
		if (u == v) {
			cout << 'B';
		} else {
			cout << mp[make_pair(u, v)];
		}
	}
	cout << endl;
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 7 ms 7524 KB Output is correct
3 Correct 9 ms 7856 KB Output is correct
4 Correct 10 ms 8148 KB Output is correct
5 Correct 10 ms 8148 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 10 ms 8148 KB Output is correct
8 Correct 10 ms 8148 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 9 ms 8148 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 7 ms 7524 KB Output is correct
3 Correct 9 ms 7856 KB Output is correct
4 Correct 10 ms 8148 KB Output is correct
5 Correct 10 ms 8148 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 10 ms 8148 KB Output is correct
8 Correct 10 ms 8148 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 9 ms 8148 KB Output is correct
11 Correct 251 ms 29268 KB Output is correct
12 Correct 311 ms 33816 KB Output is correct
13 Correct 446 ms 40688 KB Output is correct
14 Correct 496 ms 50256 KB Output is correct
15 Correct 523 ms 54348 KB Output is correct
16 Correct 804 ms 67020 KB Output is correct
17 Correct 729 ms 70692 KB Output is correct
18 Correct 777 ms 70692 KB Output is correct
19 Correct 785 ms 74612 KB Output is correct
20 Correct 299 ms 74612 KB Output is correct
21 Correct 250 ms 74612 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 7 ms 7524 KB Output is correct
3 Correct 9 ms 7856 KB Output is correct
4 Correct 10 ms 8148 KB Output is correct
5 Correct 10 ms 8148 KB Output is correct
6 Correct 8 ms 8148 KB Output is correct
7 Correct 10 ms 8148 KB Output is correct
8 Correct 10 ms 8148 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 9 ms 8148 KB Output is correct
11 Correct 251 ms 29268 KB Output is correct
12 Correct 311 ms 33816 KB Output is correct
13 Correct 446 ms 40688 KB Output is correct
14 Correct 496 ms 50256 KB Output is correct
15 Correct 523 ms 54348 KB Output is correct
16 Correct 804 ms 67020 KB Output is correct
17 Correct 729 ms 70692 KB Output is correct
18 Correct 777 ms 70692 KB Output is correct
19 Correct 785 ms 74612 KB Output is correct
20 Correct 299 ms 74612 KB Output is correct
21 Correct 250 ms 74612 KB Output is correct
22 Correct 734 ms 78320 KB Output is correct
23 Correct 735 ms 78468 KB Output is correct
24 Correct 806 ms 80728 KB Output is correct
25 Correct 704 ms 89540 KB Output is correct
26 Correct 714 ms 89540 KB Output is correct
27 Correct 722 ms 89540 KB Output is correct
28 Correct 83 ms 89540 KB Output is correct
29 Correct 305 ms 89540 KB Output is correct
30 Correct 283 ms 89540 KB Output is correct
31 Correct 320 ms 89540 KB Output is correct
32 Correct 378 ms 89540 KB Output is correct