oj.uz

답안 #51185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51185 2018-06-17T06:49:03 Z adamczh1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 8 ms 7416 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[v]) {
				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>, pair<int, int> > inp_ori;
map<pair<int, int>, char> mp;

int dfs3(int cur, int p = -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);
	bool same = (pi == inp_ori[pi]);
	if (val < 0) {
		if (same) {
			mp[inp_ori[pi]] = 'L';
		} else {
			mp[inp_ori[pi]] = 'R';
		}
	} else if (val > 0) {
		if (same) {
			mp[inp_ori[pi]] = 'R';
		} else {
			mp[inp_ori[pi]] = 'L';
		}
	} else {
		mp[inp_ori[pi]] = '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];
	}
	dfs(1);
	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
			inp_ori[make_pair(A, B)] = inp_ori[make_pair(B, A)] = make_pair(A, B);
			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]++;
	}
	dfs3(1);
	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -