oj.uz

Submission #44553

# Submission time Handle Problem Language Result Execution time Memory
44553 2018-04-03T05:45:12 Z MatheusLealV One-Way Streets (CEOI17_oneway) C++17
100 / 100
 433 ms 62668 KB 
#include <bits/stdc++.h>
#define N 100050
#define logn 20
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int q, n, m, dfsnum[N], dfslow[N], cnt, pai[N];

int anc[N][logn], used[N], nivel[N], dp[N], ans[N];

int solved[N];

vector<int> pontes;

map<pii, int> ccnt;

vector<pii> G[N], A, grafo[N];

void dfs(int x)
{
	dfsnum[x] = dfslow[x] = ++cnt;

	for(int i = 0; i< G[x].size(); i++)
	{
		int v = G[x][i].f, id = G[x][i].s;

		if(!dfsnum[v])
		{
			pai[v] = x;

			dfs(v);

			if(dfslow[v] > dfsnum[x] && ccnt[{ min(x, v), max(x, v) }] == 1 ) pontes.push_back(id);

			dfslow[x] = min(dfslow[v], dfslow[x]);
		}

		else if(v != pai[x]) dfslow[x] = min(dfsnum[v], dfslow[x]);
	}
}

int ok[N], esq[N], dir[N];

vector<pii> tree[N];

void get_tree(int x)
{
	ok[x] = 1;

	for(auto v: G[x])
	{
		if(ok[v.f]) continue;
		
		tree[x].push_back(v);

		tree[v.f].push_back({x, v.s});

		get_tree(v.f);
	}
}

int solve(int x, int p)
{
	for(auto v: tree[x])
	{
		if(v.f == p) continue;
		
		int child = solve(v.f, x);

		bool brg = binary_search(pontes.begin(), pontes.end(), v.s);

		if(child > 0 && brg)
		{
			if(esq[v.s] == x) ans[v.s] = -1;

			else ans[v.s] = 1;
		}

		else if(child < 0 && brg)
		{
			if(esq[v.s] == x) ans[v.s] = 1;

			else ans[v.s] = -1;
		}

		dp[x] += child;
	}

	solved[x] = 1;

	return dp[x];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1, a, b ;i <= m; i++)
	{
		cin>>a>>b;

		G[a].push_back({b, i - 1});

		G[b].push_back({a, i - 1});

		A.push_back({a, b});

		esq[i - 1] = a, dir[i - 1] = b;

		ccnt[ {min(a, b), max(a, b)}] ++;
	}

	for(int i = 1; i <= n; i++) if(!dfsnum[i]) dfs(i);

	for(auto id: pontes) grafo[ A[id].f ].push_back( {A[id].s, id} ), grafo[ A[id].s ].push_back( {A[id].f, id} );

	cin>>q;

	for(int i = 1, a, b; i <= q; i++)
	{
		cin>>a>>b;

		dp[a] ++, dp[b] --;
	}

	sort(pontes.begin(), pontes.end());

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

	for(int i = 1; i <= n; i++) if(!solved[i]) solve(i, i);

	for(int i = 0; i < m; i++)
	{
		if(ans[i] == 0) cout<<"B";

		else if(ans[i] > 0) cout<<"R";

		else cout<<"L";
	}

	cout<<"\n";
}

Compilation message

oneway.cpp: In function 'void dfs(int)':
oneway.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< G[x].size(); i++)
                 ~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 8 ms 7704 KB Output is correct
4 Correct 8 ms 7780 KB Output is correct
5 Correct 8 ms 7780 KB Output is correct
6 Correct 9 ms 7840 KB Output is correct
7 Correct 9 ms 7892 KB Output is correct
8 Correct 9 ms 7892 KB Output is correct
9 Correct 8 ms 7892 KB Output is correct
10 Correct 9 ms 7892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 8 ms 7704 KB Output is correct
4 Correct 8 ms 7780 KB Output is correct
5 Correct 8 ms 7780 KB Output is correct
6 Correct 9 ms 7840 KB Output is correct
7 Correct 9 ms 7892 KB Output is correct
8 Correct 9 ms 7892 KB Output is correct
9 Correct 8 ms 7892 KB Output is correct
10 Correct 9 ms 7892 KB Output is correct
11 Correct 169 ms 21724 KB Output is correct
12 Correct 187 ms 24280 KB Output is correct
13 Correct 244 ms 27628 KB Output is correct
14 Correct 295 ms 31980 KB Output is correct
15 Correct 325 ms 33916 KB Output is correct
16 Correct 382 ms 36552 KB Output is correct
17 Correct 347 ms 39460 KB Output is correct
18 Correct 390 ms 39460 KB Output is correct
19 Correct 331 ms 43244 KB Output is correct
20 Correct 183 ms 43244 KB Output is correct
21 Correct 160 ms 43244 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 8 ms 7704 KB Output is correct
4 Correct 8 ms 7780 KB Output is correct
5 Correct 8 ms 7780 KB Output is correct
6 Correct 9 ms 7840 KB Output is correct
7 Correct 9 ms 7892 KB Output is correct
8 Correct 9 ms 7892 KB Output is correct
9 Correct 8 ms 7892 KB Output is correct
10 Correct 9 ms 7892 KB Output is correct
11 Correct 169 ms 21724 KB Output is correct
12 Correct 187 ms 24280 KB Output is correct
13 Correct 244 ms 27628 KB Output is correct
14 Correct 295 ms 31980 KB Output is correct
15 Correct 325 ms 33916 KB Output is correct
16 Correct 382 ms 36552 KB Output is correct
17 Correct 347 ms 39460 KB Output is correct
18 Correct 390 ms 39460 KB Output is correct
19 Correct 331 ms 43244 KB Output is correct
20 Correct 183 ms 43244 KB Output is correct
21 Correct 160 ms 43244 KB Output is correct
22 Correct 392 ms 46412 KB Output is correct
23 Correct 368 ms 46780 KB Output is correct
24 Correct 423 ms 49556 KB Output is correct
25 Correct 433 ms 56724 KB Output is correct
26 Correct 357 ms 56724 KB Output is correct
27 Correct 371 ms 56724 KB Output is correct
28 Correct 67 ms 56724 KB Output is correct
29 Correct 199 ms 56724 KB Output is correct
30 Correct 194 ms 56724 KB Output is correct
31 Correct 236 ms 57280 KB Output is correct
32 Correct 235 ms 62668 KB Output is correct