oj.uz

Submission #65705

# Submission time Handle Problem Language Result Execution time Memory
65705 2018-08-08T12:43:29 Z polyfish One-Way Streets (CEOI17_oneway) C++14
100 / 100
 1127 ms 53564 KB 
//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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5220 KB Output is correct
3 Correct 7 ms 5388 KB Output is correct
4 Correct 7 ms 5636 KB Output is correct
5 Correct 9 ms 5712 KB Output is correct
6 Correct 8 ms 5712 KB Output is correct
7 Correct 7 ms 5788 KB Output is correct
8 Correct 7 ms 5796 KB Output is correct
9 Correct 7 ms 5796 KB Output is correct
10 Correct 9 ms 5796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5220 KB Output is correct
3 Correct 7 ms 5388 KB Output is correct
4 Correct 7 ms 5636 KB Output is correct
5 Correct 9 ms 5712 KB Output is correct
6 Correct 8 ms 5712 KB Output is correct
7 Correct 7 ms 5788 KB Output is correct
8 Correct 7 ms 5796 KB Output is correct
9 Correct 7 ms 5796 KB Output is correct
10 Correct 9 ms 5796 KB Output is correct
11 Correct 68 ms 11844 KB Output is correct
12 Correct 91 ms 13976 KB Output is correct
13 Correct 110 ms 16612 KB Output is correct
14 Correct 120 ms 21036 KB Output is correct
15 Correct 131 ms 23544 KB Output is correct
16 Correct 177 ms 31184 KB Output is correct
17 Correct 199 ms 33616 KB Output is correct
18 Correct 179 ms 33616 KB Output is correct
19 Correct 152 ms 37076 KB Output is correct
20 Correct 94 ms 37076 KB Output is correct
21 Correct 81 ms 37076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5220 KB Output is correct
3 Correct 7 ms 5388 KB Output is correct
4 Correct 7 ms 5636 KB Output is correct
5 Correct 9 ms 5712 KB Output is correct
6 Correct 8 ms 5712 KB Output is correct
7 Correct 7 ms 5788 KB Output is correct
8 Correct 7 ms 5796 KB Output is correct
9 Correct 7 ms 5796 KB Output is correct
10 Correct 9 ms 5796 KB Output is correct
11 Correct 68 ms 11844 KB Output is correct
12 Correct 91 ms 13976 KB Output is correct
13 Correct 110 ms 16612 KB Output is correct
14 Correct 120 ms 21036 KB Output is correct
15 Correct 131 ms 23544 KB Output is correct
16 Correct 177 ms 31184 KB Output is correct
17 Correct 199 ms 33616 KB Output is correct
18 Correct 179 ms 33616 KB Output is correct
19 Correct 152 ms 37076 KB Output is correct
20 Correct 94 ms 37076 KB Output is correct
21 Correct 81 ms 37076 KB Output is correct
22 Correct 1053 ms 40504 KB Output is correct
23 Correct 1127 ms 41372 KB Output is correct
24 Correct 1082 ms 43824 KB Output is correct
25 Correct 1066 ms 50464 KB Output is correct
26 Correct 1043 ms 50464 KB Output is correct
27 Correct 980 ms 50640 KB Output is correct
28 Correct 53 ms 50640 KB Output is correct
29 Correct 156 ms 50640 KB Output is correct
30 Correct 163 ms 50640 KB Output is correct
31 Correct 127 ms 50640 KB Output is correct
32 Correct 427 ms 53564 KB Output is correct