oj.uz

Submission #49111

# Submission time Handle Problem Language Result Execution time Memory
49111 2018-05-22T12:35:04 Z tmwilliamlin168 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 185 ms 51144 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, m, k, a[mxN], b[mxN], ab[mxN], d[mxN], s[mxN], p[mxN], r[mxN], dt=1, tin[mxN], low[mxN];
bool bg[mxN];
vector<int> adj1[mxN], adj2[mxN];

int find(int x) {
	return x==p[x]?x:(p[x]=find(p[x]));
}

inline void join(int x, int y) {
	if((x=find(x))==(y=find(y)))
		return;
	if(r[x]<r[y])
		p[x]=y;
	else
		p[y]=x;
	if(r[x]==r[y])
		++r[x];
}

void dfs1(int u, int p) {
//	cout << u << endl;
	tin[u]=low[u]=dt++;
	for(int e : adj1[u]) {
//		cout << "E" << e << endl;
		int v=u^ab[e];
		if(!tin[v]) {
			dfs1(v, e);
			low[u]=min(low[v], low[u]);
			if(low[v]>tin[u])
				bg[e]=1;
		} else if(e!=p)
			low[u]=min(tin[v], low[u]);
//		cout << "E" << e << endl;
	}
//	cout << u << endl;
}

void dfs2(int u, int p) {
	for(int e : adj2[u]) {
		int v=u^ab[e];
		if(v==p)
			continue;
		d[v]=d[u]+1;
		dfs2(v, u);
		s[u]+=s[v];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; ++i)
		p[i]=i;
	for(int i=0; i<m; ++i) {
		cin >> a[i] >> b[i], --a[i], --b[i];
		ab[i]=a[i]^b[i];
		adj1[a[i]].push_back(i);
		adj1[b[i]].push_back(i);
	}
	for(int i=0; i<n; ++i)
		if(!tin[i])
			dfs1(i, -1);
	for(int i=0; i<m; ++i)
		if(!bg[i])
			join(a[i], b[i]);
	for(int i=0; i<m; ++i) {
		if(!bg[i])
			continue;
		a[i]=find(a[i]);
		b[i]=find(b[i]);
		ab[i]=a[i]^b[i];
		adj2[a[i]].push_back(i);
		adj2[b[i]].push_back(i);
	}
	cin >> k;
	while(k--) {
		int x, y;
		cin >> x >> y, --x, --y;
		++s[find(x)], --s[find(y)];
//		++s[x], --s[y];
	}
	for(int i=0; i<n; ++i) {
		if(p[i]==i&&!d[i]) {
			d[i]=1;
			dfs2(i, -1);
		}
	}
	for(int i=0; i<m; ++i) {
		if(!bg[i]) {
			cout << 'B';
//			cout << endl;
			continue;
		}
		int u=d[a[i]]>d[b[i]]?a[i]:b[i];
		cout << (s[u]?((s[u]>0)==(u==a[i])?'R':'L'):'B');
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5216 KB Output is correct
3 Correct 6 ms 5280 KB Output is correct
4 Correct 7 ms 5336 KB Output is correct
5 Correct 7 ms 5408 KB Output is correct
6 Correct 6 ms 5528 KB Output is correct
7 Correct 6 ms 5596 KB Output is correct
8 Correct 7 ms 5628 KB Output is correct
9 Correct 7 ms 5628 KB Output is correct
10 Correct 6 ms 5628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5216 KB Output is correct
3 Correct 6 ms 5280 KB Output is correct
4 Correct 7 ms 5336 KB Output is correct
5 Correct 7 ms 5408 KB Output is correct
6 Correct 6 ms 5528 KB Output is correct
7 Correct 6 ms 5596 KB Output is correct
8 Correct 7 ms 5628 KB Output is correct
9 Correct 7 ms 5628 KB Output is correct
10 Correct 6 ms 5628 KB Output is correct
11 Correct 72 ms 10936 KB Output is correct
12 Correct 113 ms 13300 KB Output is correct
13 Correct 82 ms 15924 KB Output is correct
14 Correct 93 ms 18744 KB Output is correct
15 Correct 100 ms 20540 KB Output is correct
16 Correct 126 ms 22160 KB Output is correct
17 Correct 122 ms 24768 KB Output is correct
18 Correct 142 ms 24768 KB Output is correct
19 Correct 130 ms 28228 KB Output is correct
20 Correct 69 ms 28228 KB Output is correct
21 Correct 61 ms 28228 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5216 KB Output is correct
3 Correct 6 ms 5280 KB Output is correct
4 Correct 7 ms 5336 KB Output is correct
5 Correct 7 ms 5408 KB Output is correct
6 Correct 6 ms 5528 KB Output is correct
7 Correct 6 ms 5596 KB Output is correct
8 Correct 7 ms 5628 KB Output is correct
9 Correct 7 ms 5628 KB Output is correct
10 Correct 6 ms 5628 KB Output is correct
11 Correct 72 ms 10936 KB Output is correct
12 Correct 113 ms 13300 KB Output is correct
13 Correct 82 ms 15924 KB Output is correct
14 Correct 93 ms 18744 KB Output is correct
15 Correct 100 ms 20540 KB Output is correct
16 Correct 126 ms 22160 KB Output is correct
17 Correct 122 ms 24768 KB Output is correct
18 Correct 142 ms 24768 KB Output is correct
19 Correct 130 ms 28228 KB Output is correct
20 Correct 69 ms 28228 KB Output is correct
21 Correct 61 ms 28228 KB Output is correct
22 Correct 159 ms 31688 KB Output is correct
23 Correct 185 ms 32392 KB Output is correct
24 Correct 174 ms 34720 KB Output is correct
25 Correct 161 ms 41520 KB Output is correct
26 Correct 156 ms 41520 KB Output is correct
27 Correct 133 ms 41664 KB Output is correct
28 Correct 48 ms 41664 KB Output is correct
29 Correct 97 ms 41664 KB Output is correct
30 Correct 85 ms 42892 KB Output is correct
31 Correct 89 ms 45028 KB Output is correct
32 Correct 116 ms 51144 KB Output is correct