oj.uz

Submission #44551

# Submission time Handle Problem Language Result Execution time Memory
44551 2018-04-03T05:31:59 Z MatheusLealV One-Way Streets (CEOI17_oneway) C++17
0 / 100
 10 ms 8008 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;

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]) 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;
	}

	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} );//, cout<<A[id].f<<" "<<A[id].s<<'\n';

	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);
	}

	//cout<<"SPANNING TREE \n";

	//for(int x = 1; x <= n; x++)
	//{
	//	for(auto v: tree[x]) cout<<x<<" "<<v.f<<"\n";
	//}

	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:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< G[x].size(); i++)
                 ~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 10 ms 7764 KB Output is correct
4 Correct 8 ms 7764 KB Output is correct
5 Correct 9 ms 7864 KB Output is correct
6 Correct 9 ms 7932 KB Output is correct
7 Correct 9 ms 8008 KB Output is correct
8 Correct 9 ms 8008 KB Output is correct
9 Incorrect 9 ms 8008 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 10 ms 7764 KB Output is correct
4 Correct 8 ms 7764 KB Output is correct
5 Correct 9 ms 7864 KB Output is correct
6 Correct 9 ms 7932 KB Output is correct
7 Correct 9 ms 8008 KB Output is correct
8 Correct 9 ms 8008 KB Output is correct
9 Incorrect 9 ms 8008 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 10 ms 7764 KB Output is correct
4 Correct 8 ms 7764 KB Output is correct
5 Correct 9 ms 7864 KB Output is correct
6 Correct 9 ms 7932 KB Output is correct
7 Correct 9 ms 8008 KB Output is correct
8 Correct 9 ms 8008 KB Output is correct
9 Incorrect 9 ms 8008 KB Output isn't correct
10 Halted 0 ms 0 KB -