Submission #543591

#	Time	Username	Problem	Language	Result	Execution time	Memory
543591		aryan12	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	696 ms	74640 KiB

oneway

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40