oj.uz

Submission #51190

# Submission time Handle Problem Language Result Execution time Memory
51190 2018-06-17T07:22:49 Z adamczh1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 12 ms 8184 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];

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]) {
				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]);
	}
	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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 7 ms 7528 KB Output is correct
3 Correct 9 ms 7732 KB Output is correct
4 Correct 10 ms 7988 KB Output is correct
5 Correct 12 ms 7988 KB Output is correct
6 Correct 11 ms 7988 KB Output is correct
7 Correct 12 ms 8184 KB Output is correct
8 Correct 9 ms 8184 KB Output is correct
9 Incorrect 9 ms 8184 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 7 ms 7528 KB Output is correct
3 Correct 9 ms 7732 KB Output is correct
4 Correct 10 ms 7988 KB Output is correct
5 Correct 12 ms 7988 KB Output is correct
6 Correct 11 ms 7988 KB Output is correct
7 Correct 12 ms 8184 KB Output is correct
8 Correct 9 ms 8184 KB Output is correct
9 Incorrect 9 ms 8184 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 7 ms 7528 KB Output is correct
3 Correct 9 ms 7732 KB Output is correct
4 Correct 10 ms 7988 KB Output is correct
5 Correct 12 ms 7988 KB Output is correct
6 Correct 11 ms 7988 KB Output is correct
7 Correct 12 ms 8184 KB Output is correct
8 Correct 9 ms 8184 KB Output is correct
9 Incorrect 9 ms 8184 KB Output isn't correct
10 Halted 0 ms 0 KB -