oj.uz

Submission #163339

# Submission time Handle Problem Language Result Execution time Memory
163339 2019-11-12T17:37:24 Z alishahali1382 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 128 ms 18288 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
using namespace std;
typedef pair<int, int> pii;
#define pb push_back
const int MAXN = 100010;

int n, m, k, u, v, x, y, t, a, b;
int val[MAXN];
char ans[MAXN];
int E[MAXN][2];
int H[MAXN];
int comp[MAXN];
vector<pii> G[MAXN];
vector<int> G2[MAXN], bridge;

int Bridge(int node, int par, int parid){
	int res=H[node]=H[par]+1;
	for (pii p:G[node]) if (p.second!=parid){
		int v=p.first, i=p.second;
		if (H[v]){
			res=min(res, H[v]);
			ans[i]='B';
		}
		else res=min(res, Bridge(v, node, i));
	}
	if (res<H[node]){
		ans[parid]='B';
		G2[par].pb(node);
		G2[node].pb(par);
	}
	else if (parid) bridge.pb(parid);
	
	return res;
}

void dfs1(int node, int id){
	comp[node]=id;
	for (int v:G2[node]) if (!comp[v]) dfs1(v, id);
}

int dfs2(int node, int par, int parid){
	H[node]=H[par]+1;
	for (pii p:G[node]) if (p.first!=par) val[node]+=dfs2(p.first, node, p.second);
	if (val[node]==0) ans[parid]='B';
	else if (val[node]<0 ^ E[parid][0]==par) ans[parid]='L';
	else ans[parid]='R'; 
	return val[node];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<=m; i++){
		cin>>u>>v;
		E[i][0]=u, E[i][1]=v;
		G[u].pb({v, i});
		G[v].pb({u, i});
	}
	for (int i=1; i<=n; i++) if (!H[i]) Bridge(i, i, 0);
	for (int i=1; i<=n; i++) if (!comp[i]) dfs1(i, i);
	for (int i=1; i<=n; i++) G[i].clear();
	for (int i:bridge){
		E[i][0]=comp[E[i][0]];
		E[i][1]=comp[E[i][1]];
		int u=E[i][0], v=E[i][1];
		G[u].pb({v, i});
		G[v].pb({u, i});
	}
	cin>>k;
	while (k--){
		cin>>u>>v;
		u=comp[u];
		v=comp[v];
		val[u]++;
		val[v]--;
	}
	memset(H, 0, sizeof(H));
	for (int i=1; i<=n; i++) if (!H[i]) dfs2(i, i, 0);
	
	for (int i=1; i<=m; i++) cout<<ans[i]; 
	
	return 0;
}

Compilation message

oneway.cpp: In function 'int dfs2(int, int, int)':
oneway.cpp:46:20: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  else if (val[node]<0 ^ E[parid][0]==par) ans[parid]='L';
           ~~~~~~~~~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5492 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5496 KB Output is correct
4 Correct 7 ms 5496 KB Output is correct
5 Correct 7 ms 5496 KB Output is correct
6 Correct 7 ms 5496 KB Output is correct
7 Correct 7 ms 5496 KB Output is correct
8 Correct 7 ms 5496 KB Output is correct
9 Correct 7 ms 5496 KB Output is correct
10 Correct 7 ms 5496 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5492 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5496 KB Output is correct
4 Correct 7 ms 5496 KB Output is correct
5 Correct 7 ms 5496 KB Output is correct
6 Correct 7 ms 5496 KB Output is correct
7 Correct 7 ms 5496 KB Output is correct
8 Correct 7 ms 5496 KB Output is correct
9 Correct 7 ms 5496 KB Output is correct
10 Correct 7 ms 5496 KB Output is correct
11 Correct 58 ms 11612 KB Output is correct
12 Correct 71 ms 12664 KB Output is correct
13 Correct 87 ms 14172 KB Output is correct
14 Correct 101 ms 15480 KB Output is correct
15 Correct 99 ms 15376 KB Output is correct
16 Correct 74 ms 12656 KB Output is correct
17 Correct 95 ms 14168 KB Output is correct
18 Correct 104 ms 12644 KB Output is correct
19 Correct 89 ms 15216 KB Output is correct
20 Correct 77 ms 13232 KB Output is correct
21 Correct 72 ms 13032 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5492 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5496 KB Output is correct
4 Correct 7 ms 5496 KB Output is correct
5 Correct 7 ms 5496 KB Output is correct
6 Correct 7 ms 5496 KB Output is correct
7 Correct 7 ms 5496 KB Output is correct
8 Correct 7 ms 5496 KB Output is correct
9 Correct 7 ms 5496 KB Output is correct
10 Correct 7 ms 5496 KB Output is correct
11 Correct 58 ms 11612 KB Output is correct
12 Correct 71 ms 12664 KB Output is correct
13 Correct 87 ms 14172 KB Output is correct
14 Correct 101 ms 15480 KB Output is correct
15 Correct 99 ms 15376 KB Output is correct
16 Correct 74 ms 12656 KB Output is correct
17 Correct 95 ms 14168 KB Output is correct
18 Correct 104 ms 12644 KB Output is correct
19 Correct 89 ms 15216 KB Output is correct
20 Correct 77 ms 13232 KB Output is correct
21 Correct 72 ms 13032 KB Output is correct
22 Correct 112 ms 15324 KB Output is correct
23 Correct 126 ms 13784 KB Output is correct
24 Correct 128 ms 13808 KB Output is correct
25 Correct 117 ms 18288 KB Output is correct
26 Correct 113 ms 14924 KB Output is correct
27 Correct 112 ms 13812 KB Output is correct
28 Correct 45 ms 9720 KB Output is correct
29 Correct 102 ms 14072 KB Output is correct
30 Correct 99 ms 14044 KB Output is correct
31 Correct 102 ms 14340 KB Output is correct
32 Correct 108 ms 16120 KB Output is correct