oj.uz

Submission #207869

# Submission time Handle Problem Language Result Execution time Memory
207869 2020-03-09T10:30:05 Z Siberian One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 53220 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
#define int ll

struct edge{
	int to, ind;
	edge() {}
	edge(int _to, int _ind) {
		to = _to, ind = _ind;
	}
};

bool operator<(const edge & a, const edge & b) {
	return tie(a.to, a.ind) < tie(b.to, b.ind);
}

bool operator==(const edge & a, const edge & b) {
	return tie(a.to, a.ind) == tie(b.to, b.ind);
}

const int MAXN = 1e5 + 10, MAXLOG = 20;
int n, m, p;
vector<edge> g[MAXN];
vector<pair<int, int>> ed;
map<pair<int, int>, int> cnt;

void read() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		ed.push_back({u, v});
		cnt[{min(u, v), max(u, v)}]++;
		g[u].push_back({v, i});
		g[v].push_back({u, i});
	}
}

set<int> bridges;
bool used[MAXN];
int tin[MAXN], up[MAXN], timer = 0;

void dfs_bridges(int v, int p) {
	used[v] = true;
	tin[v] = up[v] = timer++;
	for (auto [to, ind] : g[v]) {
		if (to == p) continue;
		if (used[to]) {
			chkmin(up[v], tin[to]);
		}
		else {
			dfs_bridges(to, v);
			chkmin(up[v], up[to]);
			if (up[to] > tin[v] && cnt[{min(to, v), max(to, v)}] < 2) {
				bridges.insert(ind);
			}
		}
	}
}

int color[MAXN];

void dfs_color(int v, int c) {
	color[v] = c;
	for (auto [to, ind] : g[v]) {
		if (color[to] != -1) continue;
		if (bridges.count(ind)) continue;
		dfs_color(to, c);
	}
}

vector<edge> gr[MAXN];
int tout[MAXN], dp[MAXN][MAXLOG];
int Ind[MAXN];

void dfs_lca(int v, int p) {
	used[v] = true;
	tin[v] = timer++;
	dp[v][0] = p;
	for (int i = 1; i < MAXLOG; i++)
		dp[v][i] = dp[dp[v][i - 1]][i - 1];
	for (auto [i, ind] : gr[v]) {
		if (i != p) {
			Ind[i] = ind;
			dfs_lca(i, v);
		}
	}
	tout[v] = timer++;
}

bool is_upper(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int lca(int v, int u) {
	if (is_upper(v, u)) return v;
	if (is_upper(u, v)) return u;
	for (int i = MAXLOG - 1; i >= 0; i--)
		if (!is_upper(dp[v][i], u))
			v = dp[v][i];
	return dp[v][0];
}

string ans;

void build() {
	ans = "";
	for (int i = 0; i < m; i++) {
		ans += "B";
	}
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			dfs_bridges(i, -1);
		}
	}
	for (int i = 0; i < n; i++) color[i] = -1;
	
	/*cout << "bridges = " << endl;
	for (auto i : bridges)
		cout << i << " ";
	cout << endl;*/

	int c = 0;
	for (int i = 0; i < n; i++) {
		if (color[i] == -1) {
			dfs_color(i, c++);
		}
	}
	
	/*cout << "color = " << endl;
	for (int i = 0; i < n; i++) {
		cout << color[i] << " ";
	}
	cout << endl;*/

	for (auto i : bridges) {
		int u = color[ed[i].first];
		int v = color[ed[i].second];
		assert(u != v);
		gr[u].push_back({v, i});
		gr[v].push_back({u, i});
	}
	
	for (int i = 0; i < c; i++) {
		int cnt = gr[i].size();
		sort(all(gr[i]));
		gr[i].resize(unique(all(gr[i])) - gr[i].begin());
		assert(cnt == (int) gr[i].size());
	}
	
	/*cout << "gr = " << endl;
	for (int i = 0; i < c; i++) {
		cout << "i = " << i << endl;
		for (auto [to, ind] : gr[i]) {
			cout << "to = " << to << " ind = " << ind << endl;
		}
	}*/
	for (int i = 0; i < c; i++) {
		used[i] = false;
	}
	for (int i = 0; i < c; i++) {
		if (!used[i]) {
			dfs_lca(i, i);
		}
	}
}

void no() {
	assert(false);
	cout << -1 << endl;
	exit(0);
}

void make(int u, int v, int ind) {
	//cout << "make = " << u << " " << v << " " << ind << endl;
	if (color[ed[ind].first] == u && color[ed[ind].second] == v) {
		if (ans[ind] == 'L') no();
		ans[ind] = 'R';
	}
	else {
		if (ans[ind] == 'R') no();
		ans[ind] = 'L';
	}
}

void upd(int s, int f) {
	int v = color[s];
	int u = color[f];
	if (v == u) return;
	//cout << "v = " << v << " u = " << u << endl;
	while (!is_upper(v, u)) {
		make(v, dp[v][0], Ind[v]);
		v = dp[v][0];
	}
	while (!is_upper(u, v)) {
		make(dp[u][0], u, Ind[u]);
		u = dp[u][0];
	}
}

void run() {
	build();
	cin >> p;
	while (p--) {
		int s, f;
		cin >> s >> f;
		s--;
		f--;
		upd(s, f);
	}
}

void write() {
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Compilation message

oneway.cpp: In function 'void dfs_bridges(ll, ll)':
oneway.cpp:56:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [to, ind] : g[v]) {
            ^
oneway.cpp: In function 'void dfs_color(ll, ll)':
oneway.cpp:75:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [to, ind] : g[v]) {
            ^
oneway.cpp: In function 'void dfs_lca(ll, ll)':
oneway.cpp:92:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [i, ind] : gr[v]) {
            ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 9 ms 5624 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 9 ms 5496 KB Output is correct
8 Correct 9 ms 5496 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 9 ms 5240 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 9 ms 5624 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 9 ms 5496 KB Output is correct
8 Correct 9 ms 5496 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 9 ms 5240 KB Output is correct
11 Correct 132 ms 21736 KB Output is correct
12 Correct 150 ms 23144 KB Output is correct
13 Correct 182 ms 25388 KB Output is correct
14 Correct 227 ms 31716 KB Output is correct
15 Correct 253 ms 34840 KB Output is correct
16 Correct 409 ms 48868 KB Output is correct
17 Correct 541 ms 51556 KB Output is correct
18 Correct 416 ms 48996 KB Output is correct
19 Correct 480 ms 53220 KB Output is correct
20 Correct 139 ms 22500 KB Output is correct
21 Correct 123 ms 21860 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 9 ms 5496 KB Output is correct
5 Correct 9 ms 5624 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 9 ms 5496 KB Output is correct
8 Correct 9 ms 5496 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 9 ms 5240 KB Output is correct
11 Correct 132 ms 21736 KB Output is correct
12 Correct 150 ms 23144 KB Output is correct
13 Correct 182 ms 25388 KB Output is correct
14 Correct 227 ms 31716 KB Output is correct
15 Correct 253 ms 34840 KB Output is correct
16 Correct 409 ms 48868 KB Output is correct
17 Correct 541 ms 51556 KB Output is correct
18 Correct 416 ms 48996 KB Output is correct
19 Correct 480 ms 53220 KB Output is correct
20 Correct 139 ms 22500 KB Output is correct
21 Correct 123 ms 21860 KB Output is correct
22 Execution timed out 3072 ms 51556 KB Time limit exceeded
23 Halted 0 ms 0 KB -