Submission #80709

#	Time	Username	Problem	Language	Result	Execution time	Memory
80709		shoemakerjo	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	182 ms	54580 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
#define maxn 100010
#define pii pair<int, int>

vector<pii> adj[maxn];
int n, m, p;
int ans[maxn];
stack<int> cs;
int dfs_num[maxn];
int dfs_low[maxn];
int dfs_counter;
bool vis[maxn];
int pa[maxn];
int par[18][maxn];
int n1[maxn], n2[maxn]; //give the sides for each edge
int mycomp[maxn]; //just store the maximum component
int dep[maxn];

vector<pii> adj2[maxn]; //modify the adj to be for bcc labels
int cp = 0;
pii edges[maxn];

void clearstack(int val) {
	vector<int> cur; //cur is a bcc of edges
	while (!cs.empty() && cs.top() != val) {
		cur.push_back(cs.top()); cs.pop();
	}
	if (cs.size()) {
		cur.push_back(cs.top()); cs.pop();
	}
	//now we do whatever cur processing we want
	if (cur.size() < 1) {
		//then it is a bridge
		return;
	}
	//mark everything

	// cout << cp + 1 << " component:  " << endl;
	++cp;
	for (int val : cur) {
		
		// cout << "     " << val << endl;
		mycomp[val] = cp;
		// mycomp[n1[val]] = cp;
		// mycomp[n2[val]] = cp;
	}
}

void dfs(int u, int p) {
	dfs_num[u] = dfs_low[u] = dfs_counter++;
	vis[u] = true;
	int ch = 0;
	for (auto vp :  adj[u]) {
		int v = vp.first;
		int eid = vp.second;
		if (eid == p) continue;
		if (!vis[v]) {
			cs.push(v);
			ch++;
			pa[v] = u;
			dfs(v, eid);
			dfs_low[u] = min(dfs_low[u], dfs_low[v]);
			if (dfs_low[v] > dfs_num[u] ) {

				clearstack(v);
			}
		}
		else if (dfs_num[v] < dfs_num[u]) {
			dfs_low[u] = min(dfs_low[u], dfs_num[v]);
			// cs.push(eid);
		}
	}

	// cout << u << " goes to " << mycomp[u] << endl;
}

void dfsdown(int i, int p) {
	vis[i] = true;
	par[0][i] = p;
	for (pii vp : adj2[i]) {
		if (vp.first == p) continue;
		dfsdown(vp.first, i);
	}
}


int walk(int u, int k) {
	for (int i = 17; i >= 0; i--) {
		if (k & (1 << i)) {
			u = par[i][u];
		}
	}
	return u;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	u = walk(u, dep[u] - dep[v]);
	if (u == v) return 0;
	for (int i = 17; i >= 0; i--) {
		if (par[i][u] != par[i][v]) {
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][u];
}

int mydelt[maxn];

void dfsans(int u, int eid) {
	if (vis[u]) {
		// cout << "WHYYYYYY" << endl;
		return;
	}
	vis[u] = true;

	for (pii vp : adj2[u]) {
		if (vp.second == eid) continue;
		dfsans(vp.first, vp.second);
		mydelt[u] += mydelt[vp.first];
	}

	if (mydelt[u] > 0) {
		//it points upwards
		if (mycomp[n1[eid]] == u) {
			ans[eid] = 2;
		}
		else ans[eid] = 1;
	}
	else if (mydelt[u] < 0) {
		//edge points downwards
		if (mycomp[n1[eid]] == u) {
			ans[eid] = 1;
		}
		else ans[eid] = 2;
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;;

	//m pairs follow with road from a to b
	//    can be multiple edges or self-loops (throw out the latter)
	int a, b;
	int cid = 0;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		edges[i] = pii(a, b);
		++cid;

		if (a == b) continue; //we don't need this
		adj[a].push_back(pii(b, cid));
		adj[b].push_back(pii(a, cid));
		n1[cid] = a;
		n2[cid] = b;
	}
	cin >> p;

	//p pairs follow giving constraints that we must be able to go x to y


	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			pa[i] = -1;
			cs.push(i);
			dfs(i, -1);
			
			clearstack(i);

		}

	}


	for (int i = 1; i <= n; i++) {
		if (mycomp[i] == 0) mycomp[i] = ++cp;
	}

	//something like do the actual answer loop
	//first construct adj2
	for (int i = 1; i <= m; i++) {
		a = edges[i].first;
		b = edges[i].second;
		if (mycomp[a] != mycomp[b]) {
			adj2[mycomp[a]].push_back(pii(mycomp[b], i));
			adj2[mycomp[b]].push_back(pii(mycomp[a], i));
		}
	}

	fill(vis, vis+maxn, false);


	// for (int i = 1; i <= n; i++) {
	// 	cout << i << " is in " << mycomp[i] << endl;
	// }

	for (int i = 1; i <= cp; i++) {

		if (!vis[i]) dfsdown(i, -1);
	}

	for (int i = 1; i < 18; i++) {
		for (int u = 1; u <= cp; u++) {
			if (par[i-1][u] != -1) {
				par[i][u] = par[i-1][par[i-1][u]];
			}
			else par[i][u] = -1;
		}
	}
	int x, y;

	for (int i = 0; i < p; i++) {
		cin >> x >> y;
		x = mycomp[x];
		y = mycomp[y];
		int lc = lca(x, y);
		mydelt[x]++;
		mydelt[lc]--;

		mydelt[y]--;
		mydelt[lc]++;

	}

	fill(vis, vis+maxn, false);

	for (int i = 1; i <= cp; i++) {
		if (!vis[i]) dfsans(i, -1);
	}

	for (int i = 1; i <= m; i++) {
		if (ans[i] == 0) cout << "B";
		if (ans[i] == 1) cout << "L";
		if (ans[i] == 2) cout << "R";
	}
	cout << endl;
}

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