제출 #1277965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277965		g4yuhg	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	472 ms	58540 KiB

oneway

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<int, int>
#define N 100005
#define LOG 18
using namespace std;

bool ghuy4g;

struct Canh {
	ll u, v, id;
} canh[N];

pii kq[N];

vector<pii> adj[N], adj2[N];

ll n, m, q, high[N];
ll num[N], low[N], timeDfs, par[N], Par[N][LOG + 2];

bool vst[N];

void dfs2(ll u, ll parent) {
	vst[u] = 1;
	//cout << u << " high " << high[u] << endl;
	for (auto v : adj2[u]) {
		if (v.fi == parent) continue;
		Par[v.fi][0] = u;
		high[v.fi] = high[u] + 1;
		dfs2(v.fi, u);
	}
}

ll find(ll u) {
	if (par[u] < 0) return u;
	return par[u] = find(par[u]);
}

void join(ll u, ll v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (par[u] <= par[v]) {
		par[u] += par[v];
		par[v] = u;
	}
	else {
		par[v] += par[u];
		par[u] = v;
	}
}

ll mp[N], bcc, fl[N], fx[N], pl[N], px[N];
vector<ll> p[N];
vector<pii> lap;

void dfs(ll u, ll parent) {
	low[u] = num[u] = ++ timeDfs;
	for (auto vv : adj[u]) {
		ll v = vv.fi;
		if (v == parent) continue;
		if (num[v]) {
			join(u, v);
			low[u] = min(low[u], num[v]);
		}
		else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] == num[v]) {
				
			}
			else {
				join(u, v);
			}
		}
	}
}

ll lca(ll u, ll v) {
	if (high[u] > high[v]) swap(u, v);
	for (int j = LOG; j >= 0; j --) {
		if (high[v] - high[u] >= (1 << j)) {
			v = Par[v][j];
		}
	}
	if (u == v) return u;
	for (int j = LOG; j >= 0; j --) {
		if (Par[u][j] != Par[v][j]) {
			u = Par[u][j];
			v = Par[v][j];
		}
	}
	return Par[u][0];
}

ll kth_par(ll u, ll k) {
	for (int j = LOG; j >= 0; j --) {
		if (k >= (1 << j)) {
			k -= (1 << j);
			u = Par[u][j];
		}
	}
	return u;
}

void dfs3(ll u, ll parent) {
	vst[u] = 1;
	for (auto v : adj2[u]) {
		if (v.fi == parent) continue;
		dfs3(v.fi, u);
		fx[u] += fx[v.fi];
		fl[u] += fl[v.fi];
	}
}

void pre() {
	for (int i = 1; i <= n; i ++) {
		if (num[i] == 0) {
			dfs(i, i);
		}
	}
	for (auto it : lap) {
		join(it.fi, it.se);
	}
	
	map<ll, ll> mp1;
	
	for (int i = 1; i <= n; i ++) {
		ll r = find(i);
		if (mp1[r] == 0) {
			mp1[r] = ++ bcc;
		}
		mp[i] = mp1[r];
		p[mp[i]].push_back(i);
		//cout << i << " " << mp[i] << endl;
	}
	map<pii, pii> mp4;
	//cout << "bcc " << bcc << endl;
	for (int i = 1; i <= bcc; i ++) {
		for (auto u : p[i]) {
			//cout << "u " << u << endl;
			for (auto v : adj[u]) {
				//cout << "v " << v.fi << " " << v.se << endl;
				//cout << u << " " << v.fi << " " << mp[u] << " " << mp[v.fi] << endl;
				if (mp[v.fi] == mp[u]) continue;
				//cout << u << " " << v.fi << " " << mp[u] << " " << mp[v.fi] << endl;
				adj2[mp[u]].push_back({mp[v.fi], v.se});
				//cout << mp[u] << " " << mp[v.fi] << endl;
				mp4[{mp[u], mp[v.fi]}] = {u, v.fi};
				//adj2[mp[v.fi]].push_back({mp[u], v.se});
			}
		}
		//cout << endl;
	}	
	for (int i = 1; i <= bcc; i ++) {
		if (vst[i] == 0) dfs2(i, i);
	}
	for (int j = 1; j <= LOG; j ++) {
		for (int i = 1; i <= bcc; i ++) {
			ll P = Par[i][j - 1];
			Par[i][j] = Par[P][j - 1];
		}
	}
	for (int i = 1; i <= q; i ++) {
		ll u, v;
		cin >> u >> v;
		if (mp[u] == mp[v]) continue;
		u = mp[u];
		v = mp[v];
		ll x = lca(u, v);
		fl[u] ++ ;
		fl[x] -- ;
		fx[v] ++ ;
		fx[x] -- ;
	}
	for (int i = 1; i <= bcc; i ++) vst[i] = 0;
	for (int i = 1; i <= bcc; i ++) {
		if (vst[i] == 0) dfs3(i, i);
	}
	bool flag = 1;
	for (int i = 1; i <= bcc; i ++) {
		if (fx[i] > 0 && fl[i] > 0) {
			flag = 0;
			cout << -1;
			exit(0);
		}
		if (fx[i] > 0) {
			for (auto v : adj2[i]) {
				if (v.fi == Par[i][0]) {
					kq[v.se] = {mp4[{v.fi, i}].se, mp4[{v.fi, i}].fi};
				}
			}
		}
		else if (fl[i] > 0) {
			for (auto v : adj2[i]) {
				if (v.fi == Par[i][0]) {
					kq[v.se] = {mp4[{v.fi, i}].fi, mp4[{v.fi, i}].se};
				}
			}
		}
	}
	for (int i = 1; i <= m; i ++) {
		if (kq[i].fi == 0 && kq[i].se == 0) {
			cout << "B";
			continue;
		}
		if (kq[i].fi == canh[i].u) {
			cout << "L";
		}
		else {
			cout << "R";
		}
	}
}

bool klinh;

signed main() {
	memset(par, -1, sizeof(par));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	map<pii, ll> mp3;
	
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		cin >> canh[i].u >> canh[i].v;
		canh[i].id = i;
		//if (canh[i].u > canh[i].v) swap(canh[i].u, canh[i].v);
		mp3[{min(canh[i].u, canh[i].v), max(canh[i].u, canh[i].v)}] ++ ;
		if (mp3[{min(canh[i].u, canh[i].v), max(canh[i].u, canh[i].v)}] == 2) {
			lap.push_back({canh[i].u, canh[i].v});
		}
		//cout << canh[i].u << " -> " << canh[i].v << endl;
		adj[canh[i].u].push_back({canh[i].v, i});
		adj[canh[i].v].push_back({canh[i].u, i});
	}
	cin >> q;
	pre();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

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