Submission #954568

#	Time	Username	Problem	Language	Result	Execution time	Memory
954568		mocha	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	11 ms	33624 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5+5;

int n, m, q;
vector<int> g[mx];
bool vis[mx], vise[mx];
int dfn[mx], low[mx];
int t;
int ans[mx];
int p[30][mx];
int pe[mx];
int pp[mx];
int dep[mx];

// R = 1, L = 2, B = 3

struct Edge {
	int u, v;
	int id;
} e[mx];

void dfs1(int x, int pr, int d, int peg) {
	dfn[x] = low[x] = ++t;	
	p[0][x] = pr;
	dep[x] = d;
	pe[x] = peg;
	vis[x] = 1;
	for (int i:g[x]) {
		if (vise[i]) continue;
		auto [u, v, id] = e[i];
		if (u != x) swap(u, v);
		if (!vis[v]) {
			vise[i] = 1;
			dfs1(v, x, d+1, i);
			low[u] = min(low[u], low[v]);
		} else {
			low[u] = min(dfn[v], low[u]);
		}
	}
	if (low[x] != dfn[x]) {
		ans[peg] = 3;
	}
}

void dfs2(int x, int la) {
	vis[x] = 1;
	if (ans[pe[x]] or x == 1) {	
		pp[x] = la;
	} else {
		pp[x] = x;
	}
	for (int i:g[x]) {
		auto [u, v, id] = e[i];
		if (u != x) swap(u, v);
		if (vis[v]) continue;
		dfs2(v, pp[x]);
	}
}

void bdlca() {
	for (int i=1;i<30;i++) {
		for (int j=1;j<=n;j++) {
			p[i][j]	= p[i-1][p[i-1][j]];
		}
	}
}

int qlca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	int d = dep[u] - dep[v];
	for (int i=29;~i;i--) if (d&(1<<i)) u = p[i][u];
	if (u == v) return u;
	for (int i = 29; ~i; i--) {
		if (p[i][u] != p[i][v]) {
			u = p[i][u]; v = p[i][v];
		}
	}
	return p[0][u];
}

int main() {
//	cin.tie(0);ios::sync_with_stdio(0);

	cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(i);
		g[v].push_back(i);
		e[i] = {u, v, i};
	}
	dfs1(1, 0, 1, 0);
	for (int i=1;i<=n;i++) {
		vis[i] = 0;
	}
	dfs2(1, 0);
	bdlca();

	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		int lca = qlca(u, v);
		vector<int> ve;
		int lans = 0;
		while (dep[pp[u]] > dep[lca]) {
			ve.push_back(pp[u]);
			ans[pe[pp[u]]] = 1;
			u = p[0][pp[u]];
			lans = pp[u];
		}
	//	for (int i:ve) {
	//		pp[i] = lans;
	//	}
		ve.clear();
		while (dep[pp[v]] > dep[lca]) {
			ve.push_back(pp[v]);
			ans[pe[pp[v]]] = 2;
			v = p[0][pp[v]];
			lans = pp[v];
		}
	//	for (int i:ve) {
	//		pp[i] = lans;
	//	}
	}
	for (int i=1;i<=m;i++) {
		if (ans[i] == 0 or ans[i] == 3) {
			cout << 'B';
		} else if ( ans[i] == 1 ) {
			if (dep[e[i].u] < dep[e[i].v]) {
				cout << 'L';
			} else {
				cout << 'R';
			}
		} else {
			if (dep[e[i].u] < dep[e[i].v] ){
				cout << 'R';
			} else {
				cout << 'L';
			}
		}
	}
	cout << "\n";
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs1(int, int, int, int)':
oneway.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   auto [u, v, id] = e[i];
      |        ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:54:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   auto [u, v, id] = e[i];
      |        ^
oneway.cpp: In function 'int main()':
oneway.cpp:106:7: warning: variable 'lans' set but not used [-Wunused-but-set-variable]
  106 |   int lans = 0;
      |       ^~~~

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