oj.uz

Submission #45226

# Submission time Handle Problem Language Result Execution time Memory
45226 2018-04-11T23:12:43 Z Noam527 One-Way Streets (CEOI17_oneway) C++11
100 / 100
 203 ms 53684 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 3 ms 744 KB Output is correct
6 Correct 3 ms 744 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 2 ms 956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 3 ms 744 KB Output is correct
6 Correct 3 ms 744 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 2 ms 956 KB Output is correct
11 Correct 58 ms 9784 KB Output is correct
12 Correct 67 ms 12944 KB Output is correct
13 Correct 97 ms 16236 KB Output is correct
14 Correct 106 ms 20596 KB Output is correct
15 Correct 113 ms 23288 KB Output is correct
16 Correct 132 ms 27116 KB Output is correct
17 Correct 129 ms 29552 KB Output is correct
18 Correct 130 ms 29552 KB Output is correct
19 Correct 145 ms 32880 KB Output is correct
20 Correct 79 ms 32880 KB Output is correct
21 Correct 73 ms 32880 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 3 ms 744 KB Output is correct
6 Correct 3 ms 744 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 2 ms 956 KB Output is correct
11 Correct 58 ms 9784 KB Output is correct
12 Correct 67 ms 12944 KB Output is correct
13 Correct 97 ms 16236 KB Output is correct
14 Correct 106 ms 20596 KB Output is correct
15 Correct 113 ms 23288 KB Output is correct
16 Correct 132 ms 27116 KB Output is correct
17 Correct 129 ms 29552 KB Output is correct
18 Correct 130 ms 29552 KB Output is correct
19 Correct 145 ms 32880 KB Output is correct
20 Correct 79 ms 32880 KB Output is correct
21 Correct 73 ms 32880 KB Output is correct
22 Correct 203 ms 36308 KB Output is correct
23 Correct 165 ms 37400 KB Output is correct
24 Correct 178 ms 39764 KB Output is correct
25 Correct 171 ms 45800 KB Output is correct
26 Correct 169 ms 45800 KB Output is correct
27 Correct 160 ms 46708 KB Output is correct
28 Correct 44 ms 46708 KB Output is correct
29 Correct 100 ms 46708 KB Output is correct
30 Correct 94 ms 46708 KB Output is correct
31 Correct 102 ms 46708 KB Output is correct
32 Correct 126 ms 53684 KB Output is correct