oj.uz

Submission #543591

# Submission time Handle Problem Language Result Execution time Memory
543591 2022-03-30T23:04:44 Z aryan12 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 696 ms 74640 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5;

//INPUT
vector<pair<int, int> > g[N];
vector<pair<int, int> > conditions;
map<int, pair<int, int> > edge_index;

//BRIDGE FINDING
int disc[N], low[N];
set<int> bridges; //edge index
int tim = 0;
set<pair<int, int> > actually_multiple;

//DFS
bool vis[N]; //vis[edge index]
bool vis2[N];

//ANSWER
vector<int> answer(N, -2);
/*
= 0 --> B
= 1 --> R
= -1 --> L
*/

//BRIDGE TREE RELATED
int component_number[N]; //the component number of the node
vector<pair<int, int> > bridge_tree[N]; //connects component number only
int depth[N];
int DP[19][N];

//FOR UFDS
int ufds_parent[N];

int Find(int x)
{
	if(x == ufds_parent[x])
	{
		return x;
	}
	return ufds_parent[x] = Find(ufds_parent[x]);
}

void Unite(int a, int b)
{
	a = Find(a), b = Find(b);
	ufds_parent[a] = b;
}

void dfs(int node, int par)
{
	vis2[node] = true;
	disc[node] = ++tim;
	low[node] = tim;
	//cout << "node = " << node << ", time = " << tim << "\n";

	for(auto i: g[node])
	{
		int to = i.first, edge_idx = i.second;

		if(to == par)
		{
			continue;
		}

		if(vis2[to])
		{
			low[node] = min(low[node], disc[to]);
			continue;
		}

		vis[edge_idx] = true;
		dfs(to, node);
		low[node] = min(low[node], low[to]);

		if(disc[node] < low[to] && !actually_multiple.count({min(node, to), max(node, to)}))
		{
			bridges.insert(edge_idx);
		}

		/*if(node == 5 && to == 6)
		{
			cout << disc[node] << " " << low[to] << "\n";
		}*/
	}
}

//in dfs2 --> vis[node]

void dfs2(int node, int par, int component)
{
	vis[node] = true;
	component_number[node] = component;
	for(auto i: g[node])
	{
		int to = i.first, edge_idx = i.second;
		if(!vis[to] && !bridges.count(edge_idx))
		{
			dfs2(to, node, component);
		}
	}
}

void dfs_component(int node, int par)
{
	vis2[node] = true;
	for(auto i: bridge_tree[node])
	{
		int to = i.first, edge_idx = i.second;
		if(to != par)
		{
			depth[to] = depth[node] + 1;
			DP[0][to] = node;
			dfs_component(to, node);
		}
	}
}

int LCA(int x, int y)
{
	/*int f = 0;
	if(x == 2 && y == 6)
	{
		cout << "LCA: " << depth[x] << " " << depth[y] << "\n";
		f = 1;
	}*/
	if(depth[x] > depth[y])
	{
		swap(x, y);
	}
	int diff = depth[y] - depth[x];
	for(int i = 18; i >= 0; i--)
	{
		if(diff >= (1 << i))
		{
			diff -= (1 << i);
			y = DP[i][y];
		}
	}
	/*if(f == 1)
	{
		cout << "now: " << x << ", " << y << "\n";
	}*/
	if(x == y)
	{
		return x;
	}
	for(int i = 18; i >= 0; i--)
	{
		if(DP[i][x] != DP[i][y])
		{
			x = DP[i][x];
			y = DP[i][y];
		}
	}
	return DP[0][x];
}

void Solve() 
{
	int n, m;
	cin >> n >> m;

	for(int i = 1; i <= n; i++)
	{
		ufds_parent[i] = i;
	}

	set<pair<int, int> > multiple_occurrences;

	set<int> to_be_considered;

	for(int i = 1; i <= m; i++)
	{
		int u, v, f = 0;
		cin >> u >> v;

		if(u < v)
		{
			f = 1;
			swap(u, v);
		}

		if(!multiple_occurrences.count({v, u}) && v != u) //removing all multiple and self edges
		{
			multiple_occurrences.insert({v, u});
			g[u].push_back(make_pair(v, i));
			g[v].push_back(make_pair(u, i));
			to_be_considered.insert(i);
		}

		else 
		{
			answer[i] = 0;
			if(v != u)
			{
				actually_multiple.insert({v, u});
			}
		}

		if(f == 1)
		{
			swap(u, v);
		}

		edge_index[i] = {u, v};
	}

	/*for(auto i: actually_multiple)
	{
		cout << i.first << " " << i.second << "\n";
	}

	cout << "actually_multiple over" << endl;*/

	for(int i = 1; i <= n; i++)
	{
		if(!vis2[i])
		{
			dfs(i, -1);
		}
	}

	/*for(auto i: bridges)
	{
		cout << edge_index[i].first << " " << edge_index[i].second << "\n";
	}

	cout << "bridges over" << endl;*/

	for(int i = 0; i < N; i++)
	{
		vis[i] = false;
	}

	int component = 1;
	for(int i = 1; i <= n; i++)
	{
		if(!vis[i])
		{
			dfs2(i, -1, component++);
		}
	}

	for(int i = 1; i <= m; i++)
	{

		if(edge_index[i].first == edge_index[i].second || !to_be_considered.count(i))
		{
			continue;
		}

		if(component_number[edge_index[i].first] != component_number[edge_index[i].second])
		{
			bridge_tree[component_number[edge_index[i].first]].push_back(make_pair(component_number[edge_index[i].second], i));
			bridge_tree[component_number[edge_index[i].second]].push_back(make_pair(component_number[edge_index[i].first], i));
		}

		else
		{
			answer[i] = 0;
		}

	}

	int p;
	cin >> p;
	for(int i = 1; i <= p; i++)
	{
		int start, dest;
		cin >> start >> dest;
		start = component_number[start];
		dest = component_number[dest];
		
		if(start != dest)
		{
			//cout << "conditions: " << start << ", " << dest << "\n";
			conditions.push_back(make_pair(start, dest));
		}
	}

	/*for(int i = 0; i < conditions.size(); i++)
	{
		cout << conditions[i].first << " " << conditions[i].second << "\n";
	}

	for(int i = 1; i <= n; i++)
	{
		cout << component_number[i] << " ";
	}
	cout << endl;

	cout << component << "\n";

	cout << "bridge tree output\n";
	for(int i = 1; i < component; i++)
	{
		for(int j = 0; j < bridge_tree[i].size(); j++)
		{
			cout << i << " " << bridge_tree[i][j].first << "\n";
		}
	}*/

	//cout << "bye" << endl;

	for(int i = 1; i <= n; i++) 
	{
		vis2[i] = false;
	}

	for(int i = 1; i < component; i++)
	{
		if(!vis2[i])
		{
			depth[i] = 0;
			DP[0][i] = -1;
			dfs_component(i, -1);
		}
	}

	//cout << "hi" << endl;
	for(int i = 1; i < 18; i++)
	{
		for(int j = 1; j < component; j++)
		{
			if(DP[i - 1][j] == -1)
			{
				DP[i][j] = -1;
			}
			else 
			{
				DP[i][j] = DP[i - 1][DP[i - 1][j]];
			}
		}
	}

	/*for(int i = 0; i < 18; i++) 
	{
		for(int j = 1; j < component; j++)
		{
			cout << DP[i][j] << " ";
		}
		cout << "\n";
	}*/

	set<pair<int, int> > should_be_satisfied;

	//cout << "doing conditions" << endl;
	for(int i = 0; i < conditions.size(); i++)
	{
		int lca = LCA(conditions[i].first, conditions[i].second);
		int node = conditions[i].first;

		//cout << "conditions[i].first = " << conditions[i].first << ", conditions[i].second = " << conditions[i].second << ", lca = " << lca << "\n";

		node = Find(node);
		while(depth[node] > depth[lca])
		{
			should_be_satisfied.insert(make_pair(node, DP[0][node]));
			Unite(node, DP[0][node]);
			//cout << node << " -> " << DP[0][node] << "\n";
			node = Find(node);
		}

		node = Find(conditions[i].second);
		while(depth[node] > depth[lca])
		{
			should_be_satisfied.insert(make_pair(DP[0][node], node));
			//cout << node << " <- " << DP[0][node] << "\n";
			Unite(node, DP[0][node]);
			node = Find(node);
		}
	}

	//cout << "reached here" << endl;
	for(int i = 1; i <= m; i++)
	{
		int x = component_number[edge_index[i].first], y = component_number[edge_index[i].second];
		//cout << "x = " << x << ", y = " << y << "\n";
		answer[i] = 0;
		if(x != y)
		{
			if(should_be_satisfied.count({x, y}))
			{
				answer[i] = 1;
			}
			else if(should_be_satisfied.count({y, x}))
			{
				answer[i] = -1;
			}
		}
		if(actually_multiple.count({min(edge_index[i].first, edge_index[i].second), max(edge_index[i].first, edge_index[i].second)}))
		{
			answer[i] = 0;
		}
		if(answer[i] == -1)
		{
			cout << "L";
		}
		else if(answer[i] == 1)
		{
			cout << "R";
		}
		else {
			cout << "B";
		}
	}
	cout << "\n";
}

int32_t main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Solve();
	return 0;
}

Compilation message

oneway.cpp: In function 'void dfs_component(long long int, long long int)':
oneway.cpp:113:21: warning: unused variable 'edge_idx' [-Wunused-variable]
  113 |   int to = i.first, edge_idx = i.second;
      |                     ^~~~~~~~
oneway.cpp: In function 'void Solve()':
oneway.cpp:353:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  353 |  for(int i = 0; i < conditions.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 5 ms 6356 KB Output is correct
4 Correct 7 ms 6488 KB Output is correct
5 Correct 6 ms 6612 KB Output is correct
6 Correct 4 ms 6240 KB Output is correct
7 Correct 6 ms 6740 KB Output is correct
8 Correct 6 ms 6484 KB Output is correct
9 Correct 5 ms 6240 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 5 ms 6356 KB Output is correct
4 Correct 7 ms 6488 KB Output is correct
5 Correct 6 ms 6612 KB Output is correct
6 Correct 4 ms 6240 KB Output is correct
7 Correct 6 ms 6740 KB Output is correct
8 Correct 6 ms 6484 KB Output is correct
9 Correct 5 ms 6240 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 264 ms 32048 KB Output is correct
12 Correct 276 ms 33528 KB Output is correct
13 Correct 336 ms 36216 KB Output is correct
14 Correct 334 ms 42308 KB Output is correct
15 Correct 386 ms 44824 KB Output is correct
16 Correct 512 ms 57420 KB Output is correct
17 Correct 372 ms 62792 KB Output is correct
18 Correct 413 ms 57528 KB Output is correct
19 Correct 348 ms 64844 KB Output is correct
20 Correct 254 ms 33164 KB Output is correct
21 Correct 237 ms 32336 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 5 ms 6356 KB Output is correct
4 Correct 7 ms 6488 KB Output is correct
5 Correct 6 ms 6612 KB Output is correct
6 Correct 4 ms 6240 KB Output is correct
7 Correct 6 ms 6740 KB Output is correct
8 Correct 6 ms 6484 KB Output is correct
9 Correct 5 ms 6240 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 264 ms 32048 KB Output is correct
12 Correct 276 ms 33528 KB Output is correct
13 Correct 336 ms 36216 KB Output is correct
14 Correct 334 ms 42308 KB Output is correct
15 Correct 386 ms 44824 KB Output is correct
16 Correct 512 ms 57420 KB Output is correct
17 Correct 372 ms 62792 KB Output is correct
18 Correct 413 ms 57528 KB Output is correct
19 Correct 348 ms 64844 KB Output is correct
20 Correct 254 ms 33164 KB Output is correct
21 Correct 237 ms 32336 KB Output is correct
22 Correct 648 ms 69092 KB Output is correct
23 Correct 598 ms 66108 KB Output is correct
24 Correct 696 ms 66032 KB Output is correct
25 Correct 575 ms 74640 KB Output is correct
26 Correct 607 ms 68148 KB Output is correct
27 Correct 617 ms 66028 KB Output is correct
28 Correct 157 ms 14556 KB Output is correct
29 Correct 288 ms 35432 KB Output is correct
30 Correct 251 ms 35468 KB Output is correct
31 Correct 275 ms 35312 KB Output is correct
32 Correct 334 ms 46016 KB Output is correct