Submission #45226

#	Time	Username	Problem	Language	Result	Execution time	Memory
45226		Noam527	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	203 ms	53684 KiB

oneway

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

struct dsu1 {
	int n;
	vector<int> p, r;
	dsu1(int size) {
		n = size;
		p.resize(n), r.resize(n, 0);
		for (int i = 0; i < n; i++) p[i] = i;
	}
	int find(int x) {
		if (x != p[x]) p[x] = find(p[x]);
		return p[x];
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x != y) {
			if (r[x] < r[y]) p[x] = y;
			else {
				p[y] = x;
				if (r[x] == r[y]) r[x]++;
			}
		}
	}
	vector<vector<int>> calc() {
		for (int i = 0; i < n; i++) find(i);
		vector<vector<int>> a(n);
		for (int i = 0; i < n; i++) a[p[i]].push_back(i);
		vector<vector<int>> rtn;
		for (auto &i : a)
			if (i.size() > 1) rtn.push_back(i);
		return rtn;
	}
};

struct dsutree {
	int n;
	vector<int> p;
	dsutree(int size = 0) {
		n = size;
		p.resize(n);
		for (int i = 0; i < n; i++) p[i] = i;
	}
	int find(int x) {
		if (x != p[x]) p[x] = find(p[x]);
		return p[x];
	}
	void remove(int v, int par) {
		p[v] = par;
	}
};

struct edge {
	int st, to, ind;
	bool thisway;
	edge(int ss = 0, int tt = 0, int ii = -1, bool _thisway = false) {
		st = ss;
		to = tt;
		ind = ii;
		thisway = _thisway;
	}
};

int n, m, q, nn;
vector<int> dep, mn, vis;
vector<vector<edge>> g, t;
vector<vector<int>> cycles;
vector<int> incycle, par;
vector<edge> epar;

string ans;

int dfs(int v = 0, edge preve = edge(), int d = 0) {
	if (vis[v]) return dep[v];
	vis[v] = 1;
	dep[v] = d;
	mn[v] = d;
	for (const auto &i : g[v])
		if (i.ind != preve.ind)
			mn[v] = min(mn[v], dfs(i.to, i, d + 1));
	return mn[v];
}

void preprocess(int v = 0, int d = 0, edge preve = edge()) {
	if (vis[v]) return;
	//	cout << "vertex " << v << " with prev being " << preve.st << endl;
	dep[v] = d;
	vis[v] = 1;
	epar[v] = preve;
	for (const auto &i : t[v])
		preprocess(i.to, d + 1, i);
}

int main() {
	fast;
	cin >> n >> m;
	ans = string(m, 'B');
	g.resize(n);
	dep.resize(n, 0);
	mn.resize(n, 1e9);
	vis.resize(n, 0);
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		--u, --v;
		g[u].push_back(edge(u, v, i, true));
		g[v].push_back(edge(v, u, i, false));
	}

	dsu1 d1(n);
	for (int i = 0; i < n; i++)
		if (!vis[i])
			dfs(i);

	//	for (int i = 0; i < n; i++)
	//		cout << "vertex " << i << " with depth " << dep[i] << " and mn " << mn[i] << endl;

	for (const auto &i : g)
		for (const auto &j : i) {
			if (dep[j.to] > mn[j.to] && dep[j.st] < dep[j.to] && dep[j.st] >= mn[j.to]) d1.unite(j.st, j.to);
		}

	cycles = d1.calc();
	incycle.resize(n, -1);
	for (int i = 0; i < cycles.size(); i++)
		for (const auto &j : cycles[i])
			incycle[j] = i;

	nn = n + cycles.size();
	t.resize(nn);
	d1 = dsu1(nn);
	int n1, n2;
	for (const auto &i : g)
		for (const auto &j : i) {
			if (j.st < j.to) { // makes sure to count edges only once
				if (incycle[j.st] > -1) n1 = n + incycle[j.st];
				else n1 = j.st;
				if (incycle[j.to] > -1) n2 = n + incycle[j.to];
				else n2 = j.to;
				if (d1.find(n1) != d1.find(n2)) {
					d1.unite(n1, n2);
					t[n1].push_back(edge(n1, n2, j.ind, j.thisway));
					t[n2].push_back(edge(n2, n1, j.ind, !j.thisway));
				}
			}
		}
	epar.resize(nn);
	vis.resize(nn);
	dep.resize(nn);
	for (auto &i : vis) i = 0;
	for (int i = 0; i < nn; i++)
		if (!vis[i])
			preprocess(i);
	dsutree d2(nn);
	/*
	cout << "cycles" << endl;
	for (const auto &i : cycles) {
	for (const auto &j : i) cout << j << " "; cout << endl;
	}
	cout << "new tree" << endl;
	for (const auto &i : t)
		for (const auto &j : i)
			cout << j.st << " " << j.to << " with ind " << j.ind << " and direction being " << j.thisway << endl;
	cout << "parents" << endl;
	for (int i = 0; i < nn; i++)
	cout << "parent of " << i << " is " << epar[i].st << endl << "depth of " << i << " is " << dep[i] << endl;
	*/

	cin >> q;
	for (int i = 0, st, en; i < q; i++) {
		cin >> st >> en;
		--st, --en;
		if (incycle[st] != -1) st = incycle[st] + n;
		if (incycle[en] != -1) en = incycle[en] + n;
		st = d2.find(st), en = d2.find(en);
//		debug;
		while (st != en) {
//						cout << st << " " << en << endl;
			if (dep[st] > dep[en]) {
//				cout << "the way is " << epar[st].thisway << endl;
				if (epar[st].thisway) ans[epar[st].ind] = 'L';
				else ans[epar[st].ind] = 'R';
				d2.remove(st, epar[st].st);
				st = d2.find(st);
			}
			else {
//				cout << "the way is " << epar[en].thisway << endl;
				if (epar[en].thisway) ans[epar[en].ind] = 'R';
				else ans[epar[en].ind] = 'L';
				d2.remove(en, epar[en].st);
				en = d2.find(en);
			}
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:147:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < cycles.size(); i++)
                  ~~^~~~~~~~~~~~~~~

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