Submission #563708

#	Time	Username	Problem	Language	Result	Execution time	Memory
563708		ngpin04	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	132 ms	19860 KiB

oneway

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];
vector <int> g[N];

vector <int> s;

int comp[N];
int tin[N];
int tout[N];
int num[N];
int low[N];
int par[N];
int anc[N];
int fr[N];
int to[N];
int n,m,timer,nComp;

bool brd[N];
bool vis[N];

char ans[N];

bool isanc(int u, int p) {
	return tin[p] <= tin[u] && tin[u] <= tout[p];
}

int getpar(int u) {
	return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}

void dfs(int u, int p = -1) {
	num[u] = low[u] = ++timer;
	s.push_back(u);
	for (int i : adj[u]) if (i != p) {
		int v = fr[i] ^ to[i] ^ u;
		if (num[v]) {
			mini(low[u], num[v]);
		} else {
			dfs(v, i);
			mini(low[u], low[v]);
		}
	}
	
	if (num[u] == low[u]) {
		nComp++;
		int v;
		do {
			v = s.back();
			s.pop_back();
			comp[v] = nComp;
		} while (v != u);
	}
}

void solve(int u, int p = -1) {
	tin[u] = ++timer;
	anc[u] = p;
	for (int i : g[u]) if (i != p) {
		int v = fr[i] ^ to[i] ^ u;
		solve(v, i);
	}
	tout[u] = timer;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	freopen("oneway.inp","r",stdin);
	freopen("oneway.out","w",stdout);
	#endif
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> fr[i] >> to[i];
		adj[fr[i]].push_back(i);
		adj[to[i]].push_back(i);
	}
	for (int i = 1; i <= m; i++)
		ans[i] = 'B';
		
	for (int i = 1; i <= n; i++)
		if (!num[i])
			dfs(i);
	
	for (int i = 1; i <= m; i++) {
		fr[i] = comp[fr[i]];
		to[i] = comp[to[i]];
		if (fr[i] == to[i])
			continue;
		g[fr[i]].push_back(i);
		g[to[i]].push_back(i);
	}
		
	for (int i = 1; i <= n; i++)
		par[i] = -1;
		
	timer = 0;
	for (int i = 1; i <= nComp; i++)
		if (!tin[i])
			solve(i);
			
	int q; cin >> q;
	while (q--) {
		int u, v; cin >> u >> v;
		u = comp[u];
		v = comp[v];
		
		for (int i = getpar(u); !isanc(v, i);) {
			int ind = anc[i];
			ans[ind] = (fr[ind] == i) ? 'R' : 'L';
			int j = fr[ind] ^ to[ind] ^ i;
			par[i] = j;
			i = getpar(i);
		}
		
		for (int i = getpar(v); !isanc(u, i);) {
			int ind = anc[i];
			ans[ind] = (fr[ind] == i) ? 'L' : 'R';
			int j = fr[ind] ^ to[ind] ^ i;
			par[i] = j;
			i = getpar(i);
		}
	}
	
	for (int i = 1; i <= m; i++)
		cout << ans[i];
	return 0;
}

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