oj.uz

Submission #44554

# Submission time Handle Problem Language Result Execution time Memory
44554 2018-04-03T05:46:15 Z MatheusLealV One-Way Streets (CEOI17_oneway) C++17
100 / 100
 404 ms 34992 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 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 7440 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct
3 Correct 8 ms 7732 KB Output is correct
4 Correct 9 ms 7876 KB Output is correct
5 Correct 8 ms 7876 KB Output is correct
6 Correct 8 ms 7876 KB Output is correct
7 Correct 8 ms 7884 KB Output is correct
8 Correct 8 ms 7884 KB Output is correct
9 Correct 9 ms 7884 KB Output is correct
10 Correct 9 ms 7884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7440 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct
3 Correct 8 ms 7732 KB Output is correct
4 Correct 9 ms 7876 KB Output is correct
5 Correct 8 ms 7876 KB Output is correct
6 Correct 8 ms 7876 KB Output is correct
7 Correct 8 ms 7884 KB Output is correct
8 Correct 8 ms 7884 KB Output is correct
9 Correct 9 ms 7884 KB Output is correct
10 Correct 9 ms 7884 KB Output is correct
11 Correct 149 ms 20616 KB Output is correct
12 Correct 175 ms 22176 KB Output is correct
13 Correct 206 ms 24412 KB Output is correct
14 Correct 300 ms 27524 KB Output is correct
15 Correct 309 ms 28208 KB Output is correct
16 Correct 385 ms 29712 KB Output is correct
17 Correct 348 ms 31512 KB Output is correct
18 Correct 381 ms 31512 KB Output is correct
19 Correct 336 ms 32816 KB Output is correct
20 Correct 174 ms 32816 KB Output is correct
21 Correct 159 ms 32816 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7440 KB Output is correct
2 Correct 8 ms 7528 KB Output is correct
3 Correct 8 ms 7732 KB Output is correct
4 Correct 9 ms 7876 KB Output is correct
5 Correct 8 ms 7876 KB Output is correct
6 Correct 8 ms 7876 KB Output is correct
7 Correct 8 ms 7884 KB Output is correct
8 Correct 8 ms 7884 KB Output is correct
9 Correct 9 ms 7884 KB Output is correct
10 Correct 9 ms 7884 KB Output is correct
11 Correct 149 ms 20616 KB Output is correct
12 Correct 175 ms 22176 KB Output is correct
13 Correct 206 ms 24412 KB Output is correct
14 Correct 300 ms 27524 KB Output is correct
15 Correct 309 ms 28208 KB Output is correct
16 Correct 385 ms 29712 KB Output is correct
17 Correct 348 ms 31512 KB Output is correct
18 Correct 381 ms 31512 KB Output is correct
19 Correct 336 ms 32816 KB Output is correct
20 Correct 174 ms 32816 KB Output is correct
21 Correct 159 ms 32816 KB Output is correct
22 Correct 357 ms 32816 KB Output is correct
23 Correct 370 ms 32816 KB Output is correct
24 Correct 404 ms 32816 KB Output is correct
25 Correct 359 ms 34992 KB Output is correct
26 Correct 381 ms 34992 KB Output is correct
27 Correct 376 ms 34992 KB Output is correct
28 Correct 65 ms 34992 KB Output is correct
29 Correct 202 ms 34992 KB Output is correct
30 Correct 185 ms 34992 KB Output is correct
31 Correct 223 ms 34992 KB Output is correct
32 Correct 264 ms 34992 KB Output is correct