oj.uz

Submission #44547

# Submission time Handle Problem Language Result Execution time Memory
44547 2018-04-03T04:51:30 Z MatheusLealV One-Way Streets (CEOI17_oneway) C++17
0 / 100
 11 ms 12920 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]);
	}
}

void dfs2(int x, int p)
{
	used[x] = 1;

	for(auto v: grafo[x])
	{
		if(v.f == p) continue;
		
		anc[v.f][0] = x, nivel[v.f] = nivel[x] + 1;

		dfs2(v.f, x);
	}
}

int LCA(int u, int v)
{
    if(nivel[u] < nivel[v]) swap(u, v);

    for(int i = logn - 1; i >= 0; i--)
        if(nivel[u] - (1<<i) >= nivel[v])
            u = anc[u][i];

    if(u == v) return u;

    for(int i = logn - 1; i >= 0; i--)
        if(anc[u][i] != -1 && anc[u][i] != anc[v][i])
          {
              u = anc[u][i];

              v = anc[v][i];
          }

    return anc[u][0];
}

void get_tree()
{
	memset(anc, -1, sizeof anc);

	for(int i = 1; i <= n; i++) if(!used[i]) anc[i][0] = i, dfs2(i, i);

	for(int j = 1; j < logn; j++)
		for(int i = 1; i <= n; i++)
			if(anc[i][j - 1] != -1) anc[i][j] = anc[ anc[i][j - 1] ][j - 1];
}

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

		if(child > 0) 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});
	}

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

	get_tree();

	cin>>q;

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

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

	for(int i = 1; i <= n; i++)
	{
		if(solved[i] == 0) 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 Incorrect 11 ms 12920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12920 KB Output isn't correct
2 Halted 0 ms 0 KB -