Submission #108757

#	Time	Username	Problem	Language	Result	Execution time	Memory
108757		MAMBA	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	6 ms	5120 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < k; i++)
#define pb push_back

typedef long long ll;
typedef pair<int , int> pii;
typedef vector<int> vi;

template<typename S, typename T> 
inline bool smin(S &l, T r) { return l < r ? 0 : (l = r, 1); }
template<typename S, typename T> 
inline bool smax(S &l, T r) { return r < l ? 0 : (l = r, 1); }


constexpr int N = 1e5 + 10;

int n, m, p, a[N], b[N], COLOR, val[N];
vi adj[N], adj2[N];
int h[N], dp[N], inp[N], col[N];
bitset<N> mark;

void dfs2(int v, int cl, int id = -1) {
	mark[v] = true;
	if (v > 1 && col[v]) {
		adj2[cl].pb(inp[v]);	
		cl = col[v];
	}
	col[v] = cl;
	for (auto e : adj[v]) {
		if (e == id) continue;
		int u = a[e] ^ b[e] ^ v;
		if (!mark[u])
			dfs2(u , cl , e);
	}
}

void dfs(int v, int id = m) {
	mark[v] = true;
	dp[v] = h[v];
	for (auto e : adj[v]) {
		if (e == id) continue;
		int u = a[e] ^ b[e] ^ v;
		if (mark[u])
			smin(dp[v] , h[u]);
		else {
			h[u] = h[v] + 1;
			dfs(u, e);
			smin(dp[v] , dp[u]);
		}
	}
	if (dp[v] == h[v]) {
		col[v] = ++COLOR;
		inp[v] = id;
		
	}
}

char res[N];
void dfs3(int v, int id = m) {
	for (auto e : adj2[v]) {
		int u = v ^ col[a[e]] ^ col[b[e]];
		dfs3(u, e);
		val[v] += val[u];
	}
	if (val[v] == 0) return;
	res[id] = (val[v] < 0) == (col[b[id]] == v) ? 'R' : 'L';
}

int main() {
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	
	rep(i , 0 , m) {
		cin >> a[i] >> b[i];
		adj[a[i]].pb(i);
		adj[b[i]].pb(i);
	}

	dfs(1);
	mark.reset();
	dfs2(1 , COLOR);
	
	cin >> p;
	rep(i , 0 , p) {
		int u , v;
		cin >> u >> v;
		u = col[u] , v = col[v];
		if (u == v) continue;
		val[u]++;
		val[v]--;
	}

	memset(res , 'B', sizeof(res));
	dfs3(COLOR);
	rep(i , 0 , m) 
		cout << res[i];

	return 0;
}

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