oj.uz

Submission #80709

# Submission time Handle Problem Language Result Execution time Memory
80709 2018-10-22T04:08:54 Z shoemakerjo One-Way Streets (CEOI17_oneway) C++14
100 / 100
 182 ms 54580 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5244 KB Output is correct
3 Correct 6 ms 5560 KB Output is correct
4 Correct 7 ms 5676 KB Output is correct
5 Correct 7 ms 5700 KB Output is correct
6 Correct 6 ms 5700 KB Output is correct
7 Correct 7 ms 5728 KB Output is correct
8 Correct 7 ms 5772 KB Output is correct
9 Correct 7 ms 5828 KB Output is correct
10 Correct 6 ms 5828 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5244 KB Output is correct
3 Correct 6 ms 5560 KB Output is correct
4 Correct 7 ms 5676 KB Output is correct
5 Correct 7 ms 5700 KB Output is correct
6 Correct 6 ms 5700 KB Output is correct
7 Correct 7 ms 5728 KB Output is correct
8 Correct 7 ms 5772 KB Output is correct
9 Correct 7 ms 5828 KB Output is correct
10 Correct 6 ms 5828 KB Output is correct
11 Correct 61 ms 12868 KB Output is correct
12 Correct 64 ms 14984 KB Output is correct
13 Correct 65 ms 17704 KB Output is correct
14 Correct 90 ms 21888 KB Output is correct
15 Correct 94 ms 24288 KB Output is correct
16 Correct 119 ms 30700 KB Output is correct
17 Correct 110 ms 33568 KB Output is correct
18 Correct 133 ms 33568 KB Output is correct
19 Correct 108 ms 36900 KB Output is correct
20 Correct 63 ms 36900 KB Output is correct
21 Correct 60 ms 36900 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5244 KB Output is correct
3 Correct 6 ms 5560 KB Output is correct
4 Correct 7 ms 5676 KB Output is correct
5 Correct 7 ms 5700 KB Output is correct
6 Correct 6 ms 5700 KB Output is correct
7 Correct 7 ms 5728 KB Output is correct
8 Correct 7 ms 5772 KB Output is correct
9 Correct 7 ms 5828 KB Output is correct
10 Correct 6 ms 5828 KB Output is correct
11 Correct 61 ms 12868 KB Output is correct
12 Correct 64 ms 14984 KB Output is correct
13 Correct 65 ms 17704 KB Output is correct
14 Correct 90 ms 21888 KB Output is correct
15 Correct 94 ms 24288 KB Output is correct
16 Correct 119 ms 30700 KB Output is correct
17 Correct 110 ms 33568 KB Output is correct
18 Correct 133 ms 33568 KB Output is correct
19 Correct 108 ms 36900 KB Output is correct
20 Correct 63 ms 36900 KB Output is correct
21 Correct 60 ms 36900 KB Output is correct
22 Correct 168 ms 40316 KB Output is correct
23 Correct 167 ms 41176 KB Output is correct
24 Correct 182 ms 43680 KB Output is correct
25 Correct 156 ms 50308 KB Output is correct
26 Correct 160 ms 50308 KB Output is correct
27 Correct 177 ms 50504 KB Output is correct
28 Correct 80 ms 50504 KB Output is correct
29 Correct 94 ms 50504 KB Output is correct
30 Correct 97 ms 50504 KB Output is correct
31 Correct 103 ms 50504 KB Output is correct
32 Correct 108 ms 54580 KB Output is correct