oj.uz

답안 #411777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411777 2021-05-25T22:40:31 Z penguinhacker One-Way Streets (CEOI17_oneway) C++14
0 / 100
 9 ms 10188 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, m, k, eu[mxN], ev[mxN], t, ecc, tin[mxN], low[mxN], who[mxN], d[mxN], anc[mxN][17], dp[mxN][2];
vector<int> adj[mxN];
stack<int> st;
vector<ar<int, 2>> br, adj2[mxN];
char ans[mxN];

void make(int u) {
	who[u]=ecc;
	while(st.top()^u)
		who[st.top()]=ecc, st.pop();
	st.pop(), ++ecc;
}

void dfs(int u, int p=-1) {
	tin[u]=low[u]=++t;
	st.push(u);
	for (int i : adj[u]) {
		if (i==p)
			continue;
		int v=u^eu[i]^ev[i];
		if (!tin[v]) {
			dfs(v, i);
			low[u]=min(low[u], low[v]);
			if (low[v]>tin[u]) {
				br.push_back({i, u==eu[i]});
				make(v);
			}
		} else
			low[u]=min(low[u], tin[v]);
	}
}

void dfs2(int u, int p=-1) {
	anc[u][0]=p;
	for (int i=1; i<17; ++i)
		anc[u][i]=anc[u][i-1]^-1?anc[anc[u][i-1]][i-1]:-1;
	for (ar<int, 2> x : adj2[u]) {
		int v=u^who[eu[x[0]]]^who[ev[x[0]]];
		d[v]=d[u]+1;
		dfs2(v, u);
	}
}

int lca(int u, int v) {
	if (d[u]>d[v])
		swap(u, v);
	for (int i=16; ~i; --i)
		if (d[u]<=d[v]-(1<<i))
			v=anc[v][i];
	if (u==v)
		return u;
	for (int i=16; ~i; --i)
		if (anc[u][i]^anc[v][i])
			u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}

void dfs3(int u) {
	for (ar<int, 2> x : adj2[u]) {
		int v=u^who[eu[x[0]]]^who[ev[x[0]]];
		dfs3(v);
		dp[u][0]+=dp[v][0];
		dp[u][1]+=dp[v][1];
		assert(!(dp[v][0]&&dp[v][1]));
		if (dp[v][0]||dp[v][1])
			ans[x[0]]=x[1]^(dp[v][0]>0)?'R':'L';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		cin >> eu[i] >> ev[i], --eu[i], --ev[i];
		if (eu[i]^ev[i]) {
			adj[eu[i]].push_back(i);
			adj[ev[i]].push_back(i);
		}
	}
	for (int i=0; i<n; ++i) {
		if (tin[i])
			continue;
		dfs(i);
		make(i);
		for (ar<int, 2> b : br) {
			int u=b[1]?eu[b[0]]:ev[b[0]];
			adj2[who[u]].push_back(b);
		}
		dfs2(who[i]);
	}
	cin >> k;
	for (int i=0; i<k; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		u=who[u], v=who[v];
		int uv=lca(u, v);
		++dp[u][0], --dp[uv][0];
		++dp[v][1], --dp[uv][1];
	}
	memset(ans, 'B', m);
	for (int i=0; i<ecc; ++i)
		if (anc[i][0]==-1)
			dfs3(i);
	for (int i=0; i<m; ++i)
		cout << ans[i];
	return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 10188 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 10188 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 10188 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -