Submission #207869

#	Time	Username	Problem	Language	Result	Execution time	Memory
207869		Siberian	One-Way Streets (CEOI17_oneway)	C++14	60 / 100	3072 ms	53220 KiB

oneway

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

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