Submission #411771

#	Time	Username	Problem	Language	Result	Execution time	Memory
411771		penguinhacker	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	9 ms	10080 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, m, k, eu[mxN], ev[mxN], t, ecc, tin[mxN], low[mxN], who[mxN], d[mxN], anc[mxN][17], dp[mxN][2];
vector<int> adj[mxN];
stack<int> st;
vector<ar<int, 2>> br, adj2[mxN];
char ans[mxN];

void make(int u) {
	who[u]=ecc;
	while(st.top()^u)
		who[st.top()]=ecc, st.pop();
	st.pop(), ++ecc;
}

void dfs(int u, int p=-1) {
	tin[u]=low[u]=++t;
	st.push(u);
	for (int i : adj[u]) {
		if (i==p)
			continue;
		int v=u^eu[i]^ev[i];
		if (!tin[v]) {
			dfs(v, i);
			low[u]=min(low[u], low[v]);
			if (low[v]>tin[u]) { // bridge
				//cout << "bridge: " << u << " " << v << endl;
				br.push_back({i, u==eu[i]});
				make(v);
			}
		} else
			low[u]=min(low[u], tin[v]);
	}
}

void dfs2(int u, int p=-1) {
	//cout << u << endl;
	anc[u][0]=p;
	for (int i=1; i<17; ++i)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for (ar<int, 2> x : adj2[u]) {
		int v=u^who[eu[x[0]]]^who[ev[x[0]]];
		d[v]=d[u]+1;
		dfs2(v, u);
	}
}

int lca(int u, int v) {
	if (d[u]>d[v])
		swap(u, v);
	for (int i=16; ~i; --i)
		if (d[u]<=d[v]-(1<<i))
			v=anc[v][i];
	if (u==v)
		return u;
	for (int i=16; ~i; --i)
		if (anc[u][i]^anc[v][i])
			u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}

void dfs3(int u) {
	for (ar<int, 2> x : adj2[u]) {
		int v=u^who[eu[x[0]]]^who[ev[x[0]]];
		dfs3(v);
		dp[u][0]+=dp[v][0];
		dp[u][1]+=dp[v][1];
		assert(!(dp[v][0]&&dp[v][1]));
		if (dp[v][0]||dp[v][1])
			ans[x[0]]=x[1]^dp[v][0]>0?'R':'L';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		cin >> eu[i] >> ev[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	for (int i=0; i<n; ++i) {
		if (tin[i])
			continue;
		dfs(i);
		make(i);
		for (ar<int, 2> b : br) {
			int u=b[1]?eu[b[0]]:ev[b[0]];
			adj2[who[u]].push_back(b);
		}
		dfs2(who[i]);
	}
	cin >> k;
	for (int i=0; i<k; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		u=who[u], v=who[v];
		int uv=lca(u, v);
		++dp[u][0], --dp[uv][0];
		++dp[v][1], --dp[uv][1];
	}
	memset(ans, 'B', m);
	for (int i=0; i<ecc; ++i)
		if (anc[i][0]==-1)
			dfs3(i);
	for (int i=0; i<m; ++i)
		cout << ans[i];
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:75:27: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   75 |    ans[x[0]]=x[1]^dp[v][0]>0?'R':'L';
      |                   ~~~~~~~~^~

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