제출 #938407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938407		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	5 ms	7260 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
	return a < b ? (a = b) == b : false;
}
const int N = 1e5 + 1;

vector<vector<int>> g(N);
bool vis[N];
int parent[N];

void dfs(int v, int p) {
	vis[v] = true;
	parent[v] = p;
	for (int to : g[v]) {
		if (!vis[to]) {
			dfs(to, v);
		}
	}
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m; cin >> n >> m;
	int a[m], b[m];
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i];
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	int p; cin >> p;
	int u[p], v[p];
	map<pair<int, int>, bool> used;
	for (int i = 0; i < p; ++i) {
		cin >> u[i] >> v[i];
		dfs(u[i], -1);
		vector<int> path;
		int x = v[i];
		while (x != -1) {
			path.push_back(x);
			x = parent[x];
		}
		reverse(all(path));
		for (int i = 1; i < size(path); ++i) {
			used[{path[i - 1], path[i]}] = true;
			g[path[i]].erase(find(all(g[path[i]]), path[i - 1]));
		}
		memset(vis, false, sizeof(vis));
		memset(parent, 0, sizeof(parent));
	}
	for (int i = 0; i < m; ++i) {
		if (used[{a[i], b[i]}]) {
			cout << 'R';
		} else if (used[{b[i], a[i]}]) {
			cout << 'L';
		} else {
			cout << 'B';
		}
	}
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40