Submission #938423

#	Time	Username	Problem	Language	Result	Execution time	Memory
938423		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	4440 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<pair<int, int>>> g(N);
bool vis[N];
int parent[N], indp[N];
map<array<int, 3>, int> used;

void dfs(int v) {
	vis[v] = true;
	for (auto [to, ind] : g[v]) {
		if (!vis[to] && (used[{v, to, ind}] || !used[{to, v, ind}])) {
			parent[to] = v;
			indp[to] = ind;
			dfs(to);
		}
	}
}

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], i});
		g[b[i]].push_back({a[i], i});
	}
	int p; cin >> p;
	int u[p], v[p];
	for (int i = 0; i < p; ++i) {
		cin >> u[i] >> v[i];
		dfs(u[i]);
		vector<int> path, inde;
		int x = v[i];
		while (x) {
			path.push_back(x);
			inde.push_back(indp[x]);
			x = parent[x];
		}
		inde.pop_back();
		reverse(all(path));
		reverse(all(inde));
		for (int i = 1; i < size(path); ++i) {
			used[{path[i - 1], path[i], inde[i - 1]}] = true;
		}
		memset(vis, false, sizeof(vis));
		memset(parent, 0, sizeof(parent));
		memset(indp, 0, sizeof(indp));
	}
	for (int i = 0; i < m; ++i) {
		if (used[{a[i], b[i], i}]) {
			cout << 'R';
		} else if (used[{b[i], a[i], i}]) {
			cout << 'L';
		} else {
			cout << 'B';
		}
	}
}

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