Submission #65705

#	Time	Username	Problem	Language	Result	Execution time	Memory
65705		polyfish	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	1127 ms	53564 KiB

oneway

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 100002;
const int LG_N = 19;
const int INF = 1e9;

struct edge {
	int u, v;
};

int n, m, nTime, num[MAX_N], low[MAX_N], l[MAX_N], p[LG_N+2][MAX_N];
int nCC, cc_id[MAX_N], up_query[MAX_N], down_query[MAX_N];
bool bridge[MAX_N], visited[MAX_N];
edge e[MAX_N];
vector<pair<int, int> > g[MAX_N], tr[MAX_N];
char res[MAX_N];

void enter() {
	cin >> n >> m;
	for (int i=1; i<=m; ++i) {
		cin >> e[i].u >> e[i].v;
		g[e[i].u].push_back(make_pair(e[i].v, i));
		g[e[i].v].push_back(make_pair(e[i].u, i));
	}
}

void dfs(int u, int par) {
	num[u] = low[u] = ++nTime;
	bool ok = false;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i].first, id = g[u][i].second;
		if (v==par && !ok)
			ok = true;
		else {
			if (num[v])
				low[u] = min(low[u], num[v]);
			else {
				dfs(v, u);
				low[u] = min(low[u], low[v]);
			}
			if (num[u]<low[v])
				bridge[id] = true;
			else
				res[id] = 'B';
		}
	}
}

void find_connected_component(int u) {
	cc_id[u] = nCC;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i].first, id = g[u][i].second;
		if (cc_id[v]==0 && !bridge[id])
			find_connected_component(v);
	}
}

void fix_root(int u) {
	for (int i=0; i<tr[u].size(); ++i) {
		int v = tr[u][i].first;
		if (v!=p[0][u]) {
			p[0][v] = u;
			l[v] = l[u] + 1;
			fix_root(v);
		}
	}
}

void init_tree() {
	for (int i=1; i<=n; ++i)
		if (num[i]==0)
			dfs(i, 0);
	for (int i=1; i<=n; ++i) {
		if (cc_id[i]==0) {
			++nCC;
			find_connected_component(i);
		}
	}
	//PR(bridge, m);
	for (int i=1; i<=m; ++i) {
		if (bridge[i]) {
			int u = cc_id[e[i].u], v = cc_id[e[i].v];
			tr[u].push_back(make_pair(v, i));
			tr[v].push_back(make_pair(u, i));
		}
	}
	n = nCC;
	for (int i=1; i<=n; ++i) {
		if (l[i]==0) {
			l[i] = 1;
			fix_root(i);
		}
	}
	for (int i=1; i<=LG_N; ++i)
		for (int j=1; j<=n; ++j)
			p[i][j] = p[i-1][p[i-1][j]];
}

int lca(int x, int y) {
	for (int k=LG_N; k>=0; --k)
		if (l[p[k][x]]>=l[y])
			x = p[k][x];
	for (int k=LG_N; k>=0; --k)
		if (l[p[k][y]]>=l[x])
			y = p[k][y];
	for (int k=LG_N; k>=0; --k) {
		if (p[k][x]!=p[k][y]) {
			x = p[k][x];
			y = p[k][y];
		}
	}
	while (x != y) {
		x = p[0][x];
		y = p[0][y];
	}
	return x;
}

void init_query() {
	int nQuery;
	cin >> nQuery;
	while (nQuery--) {
		int u, v;
		cin >> u >> v;
		u = cc_id[u], v = cc_id[v];
		if (u!=v) {
			//cerr << u << ' ' << v << '\n';
			int anc = lca(u, v);
			++up_query[u];
			--up_query[anc];
			++down_query[v];
			--down_query[anc];
		}
	}
}

void solve(int u) {
	visited[u] = true;
	for (int i=0; i<tr[u].size(); ++i) {
		int v = tr[u][i].first, id = tr[u][i].second;
		if (v!=p[0][u]) {
			solve(v);
			up_query[u] += up_query[v];
			down_query[u] += down_query[v];
			if (up_query[v]>0)
				res[id] = (make_pair(cc_id[e[id].u], cc_id[e[id].v])==make_pair(v, u) ? 'R' : 'L');
			else if (down_query[v]>0)
				res[id] = (make_pair(cc_id[e[id].u], cc_id[e[id].v])==make_pair(u, v) ? 'R' : 'L');
			else
				res[id] = 'B';
		}
	}
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	init_tree();
	init_query();
	for (int i=1; i<=n; ++i)
		if (!visited[i])
			solve(i);
	for (int i=1; i<=m; ++i)
		cout << res[i];
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
oneway.cpp: In function 'void find_connected_component(int)':
oneway.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
oneway.cpp: In function 'void fix_root(int)':
oneway.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<tr[u].size(); ++i) {
                ~^~~~~~~~~~~~~
oneway.cpp: In function 'void solve(int)':
oneway.cpp:148:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<tr[u].size(); ++i) {
                ~^~~~~~~~~~~~~

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