Submission #1022658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022658		JuliaTatad	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	348 KiB

oneway

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>

using namespace std;

int n, m, p; 
int INF = 2 * 1e9;
vector<vector<int>> gr;
vector<bool> used;
vector<int> comp; vector<vector<int>> cgr;
vector<int> d, dp;
vector<char> sol;
set<pair<int, int>> done;
vector<vector<int>> mp;
vector<int> bridges; 
vector<int> ts; vector<bool> vis;
multiset<int> x; multiset<int> y;


map<pair<int, int>, pair<char, int>> translate;
vector<int> parents;

struct Edge {
	int from, to, num; bool is_bridge;
	Edge() {}
	Edge(int from, int to, int num) : from(from), to(to), num(num), is_bridge(false) {}
};

vector<Edge> edges;

void dfs(int v, int pnum = -1, int p = -1) {
	used[v] = true;
	if (p == -1) {
		d[v] = 0;
	}
	else {
		d[v] = d[p] + 1;
	}
	dp[v] = INF;
	for (auto e : gr[v]) {
		Edge cur = edges[e];
		sol[cur.num] = 'B'; 
		if (!used[cur.to]) {
			dfs(cur.to, cur.num, v); dp[v] = min(dp[v], dp[cur.to]);
		}
		else if (pnum != cur.num) {
			dp[v] = min(dp[v], d[cur.to]);
		}
	}
	if (pnum != -1 && dp[v] >= d[v]) {
		edges[2 * pnum].is_bridge = true; edges[2 * pnum + 1].is_bridge = true;
		bridges.push_back(pnum);
	}
}

void dfs2(int v, int cur_comp) {
	comp[v] = cur_comp;
	for (auto e : gr[v]) {
		Edge cur = edges[e];
		if (!cur.is_bridge && comp[cur.to] == -1) {
			dfs2(cur.to, cur_comp);
		}
		else if (comp[cur.to] != -1 && cur.is_bridge) {
			cgr[cur_comp].push_back(comp[cur.to]); cgr[comp[cur.to]].push_back(cur_comp);
		}
	}
}

void dfsts(int v) {
	vis[v] = true;
	for (auto u : mp[v]) {
		if (!vis[u]) {
			parents[u] = v;
			dfsts(u);
		}
	}
	ts.push_back(v);
}

int main() {
	cin >> n >> m;
	gr.resize(n); sol.resize(m); d.resize(n); dp.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b; a--; b--;
		edges.push_back(Edge(a, b, i)); edges.push_back(Edge(b, a, i));
		gr[a].push_back(2 * i); gr[b].push_back(2 * i + 1);
	}

	used.assign(n, false);
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			dfs(i);
		}
	}

	//cout << "done dfs1" << endl;

	comp.resize(n, -1); int cur_comp = 0;
	for (int i = 0; i < n; i++) {
		if (comp[i] == -1) {
			cgr.push_back(vector<int>()); dfs2(i, cur_comp++);
		}
	}

	//cout << "done dfs2 " << endl;

	mp.resize(cur_comp);
	for (int bridge : bridges) {
		mp[comp[edges[2*bridge].from]].push_back(comp[edges[2*bridge].to]);
		mp[comp[edges[2*bridge].to]].push_back(comp[edges[2*bridge].from]);
		translate[{comp[edges[2 * bridge].from], comp[edges[2 * bridge].to]}] = { 'R', bridge };
		translate[{comp[edges[2 * bridge].to], comp[edges[2 * bridge].from]}] = { 'L', bridge };
	}

	vis.assign(cur_comp, false); parents.resize(cur_comp);
	for (int i = 0; i < cur_comp; i++) {
		if (!vis[i]) {
			dfsts(i);
		}
	}

	//cout << "done dfs3" << endl;

	cin >> p;
	for (int i = 0; i < p; i++) {
		int a, b; cin >> a >> b; a--; b--;
		if (comp[a] != comp[b]) {
			x.insert(comp[a]); y.insert(comp[b]); 
		}
	}

	//cout << "taken input " << endl;

	for (int i = 0; i < cur_comp; i++) {
		if (x.count(ts[i]) > 0) {
			x.erase(ts[i]); x.insert(parents[ts[i]]);
			sol[translate[{ts[i], parents[ts[i]]}].second] = translate[{ts[i], parents[ts[i]]}].first;
		}
		if (y.count(ts[i]) > 0) {
			y.erase(ts[i]); y.insert(parents[ts[i]]); 
			sol[translate[{parents[ts[i]], ts[i]}].second] = translate[{parents[ts[i]], ts[i]}].first;
		}
		while (x.count(parents[ts[i]]) > 0 && y.count(parents[ts[i]]) > 0) {
			x.erase(parents[ts[i]]); y.erase(parents[ts[i]]); 
		}
	}

	//cout << "part 4" << endl;

	for (int i = 0; i < sol.size(); i++) {
		cout << sol[i];
	}
	cout << "\n";

}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 0; i < sol.size(); i++) {
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40