제출 #958443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958443		dio_2	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	461 ms	61616 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

// DESCRIPTION
// Given an undirected graph returns a forest 
// where every node in a tree is a potential SCC in the initial graph.
// Works with multi-edges and disconnected components.
// Doesnt acctually orient the edges to make the SCC since 
// The forest only considers them as nodes.
// You don't really have a connection with the previous graph.
// 0 - indexed.
// check: https://codeforces.com/contest/555/problem/E.
// Watch out for:
// 1) multi-edges.
// 2) how many components.
// 3) carefull implementation.
vector<vector<int>> Get2EdgeForest(vector<vector<pii>> &g, int n, int m, int &N, vector<int> &labels, vector<pii> &bri){
	vector<int> vis(n), dep(n), is_span(m), dp(n), is_bridge(m);
	vector<vector<int>> gA(n), gB(n);
	vector<pii> bridges;
	
	// finding bridges and marking them
	auto dfs = [&](auto &&dfs, int u, int p, int id)->void{
		vis[u] = 1;
		for(auto [v, i] : g[u]) if(!vis[v]){
			dep[v] = dep[u] + 1;
			is_span[i] = 1;
			dfs(dfs, v, u, i); // DFS AFTER DEPTH CALCULATION!!!!!!!.
		}
		int cnt_par = 0;
		set<int> s; // UGLY with sets can be done without ' em.
		for(auto [v, i] : g[u]){ 
			if(v == p){
				cnt_par += 1;
				continue;
			}
			if(s.count(v)) continue;
			s.insert(v);
			if(is_span[i]) dp[u] += dp[v];
			if(!is_span[i] && dep[v] > dep[u]) dp[u]--;
			if(!is_span[i] && dep[v] < dep[u]) dp[u]++;
		}
		// cnt_par == 1 needed for multiple edges.
		if(dp[u] == 0 && p != -1 && cnt_par == 1){
			bridges.emplace_back(u, p);
			is_bridge[id] = 1;
		}
	}; 
	
	for(int i = 0;i < n;i++){
		if(!vis[i]){
			dfs(dfs, i, -1, -1);
		}
	}
	
	// ceating a second graph without bridges
	for(int i = 0;i < n;i++){
		for(auto [j, id] : g[i]){
			if(is_bridge[id]) continue;
			gA[i].push_back(j);
		}
	}

	vector<int> label(n);
	fill(vis.begin(), vis.end(), false);
	int cnt = 0;
	
	// merge nodes.
	auto dfs2 = [&](auto &&dfs2, int u)->void{
		vis[u] = 1;
		label[u] = cnt;
		for(int v : gA[u]){
			if(!vis[v]){
				dfs2(dfs2, v);
			}
		}
	};
	
	for(int i = 0;i < n;i++){
		if(!vis[i]){
			dfs2(dfs2, i);
			cnt++;
		}
	}
	
	// create the tree.
	for(auto [u, v] : bridges){
		int orgu = u, orgv = v;
		u = label[u];
		v = label[v];
		if(u == v) continue;
		bri.emplace_back(orgu, orgv);
		gB[u].push_back(v);
		gB[v].push_back(u);
	}
	
	N = cnt;
	labels = label;
	return gB;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	
	vector<vector<pair<int, int>>> g(n);
	vector<pii> E(m);
	string ans(m, 'B');
	for(int i = 0;i < m;i++){
		int a, b;
		cin >> a >> b, --a, --b;
		if(a == b){
			ans[i] = 'B';
		} else {
			g[a].emplace_back(b, i);
			g[b].emplace_back(a, i);
		}
		E[i] = make_pair(a, b);
	}
	
	int p;
	cin >> p;
	vector<pair<int, int>> a(p);
	for(int i = 0;i < p;i++){
		int x, y;
		cin >> x >> y, --x, --y;
		a[i] = make_pair(x, y);
	}
	
	int N;
	vector<int> labels;
	vector<pii> bri;
	map<pii, pii> mapka;
	map<pii, pii> ord;
	map<pii, bool> is;
	vector<vector<int>> new_g = Get2EdgeForest(g, n, m, N, labels, bri);
	vector<bool> vis(N);
	
	for(auto [x, y] : bri){
		mapka[make_pair(labels[x], labels[y])] = make_pair(x, y);
		is[make_pair(x, y)] = true;
	}
	const int LOG = 20;
	vector<vector<int>> up(N, vector<int> (LOG));
	vector<int> dep(N);
	vector<int> L(N), A(N), B(N);
	auto dfs = [&](auto &&dfs, int u, int p)->void{
		vis[u] = 1;
		for(int v : new_g[u]) if(v != p){
			dep[v] = dep[u] + 1;
			up[v][0] = u;
			for(int i = 1;i < LOG;i++) up[v][i] = up[ up[v][i - 1] ][i - 1];
			dfs(dfs, v, u);
		}
	};
	
	auto lca = [&](int u, int v)->int{
		if(dep[u] > dep[v]) swap(v, u);
		int k = dep[v] - dep[u];
		for(int i = LOG - 1;i >= 0;i--){
			if((k >> i) & 1) v = up[v][i];
		}
		assert(dep[v] == dep[u]);
		if(v == u) return v;
		for(int i = LOG - 1;i >= 0;i--){
			if(up[v][i] != up[u][i]){
				u = up[u][i];
				v = up[v][i];
			}
		}
		assert(up[v][0] == up[u][0]);
		return up[v][0];
	};
	
	for(int i = 0;i < N;i++){
		if(!vis[i]){
			for(int j = 0;j < LOG;j++) up[i][j] = i;
			dfs(dfs, i, -1);
		}
	}
	
	for(auto &[x, y] : a){ // x -> y.
		x = labels[x];
		y = labels[y];
		int l = lca(x, y);
		if(x == y) continue;
		L[l]++;
		A[x]++;
		B[y]++;
	}
	
	auto dfs2 = [&](auto &&dfs2, int u, int p)->void{
		for(int v : new_g[u]) if(v != p){
			dfs2(dfs2, v, u);
			A[u] += A[v];
			B[u] += B[v];
			L[u] += L[v];
		}
		if(p != -1){
			assert(not(A[u] - L[u] > 0 && B[u] - L[u] > 0));
			pii real;
			if(mapka.find(make_pair(u, p)) != mapka.end()){
				real = mapka[make_pair(u, p)];
			} else {
				real = mapka[make_pair(p, u)];
			}
			int _a = real.first;
			int _b = real.second;
			if(labels[_a] != p) swap(_a, _b);
			// _a is parent _b in bridge tree.
			if(A[u] - L[u] > 0){
				ord[real] = make_pair(_b, _a);
			} else if(B[u] - L[u] > 0){
				ord[real] = make_pair(_a, _b);
			} else {
				ord[real] = make_pair(-1, -1);
			}
		}
	};
	
	for(int i = 0;i < N;i++){
		if(dep[i] == 0){
			dfs2(dfs2, i, -1);
		}
	}
	
	for(int i = 0;i < m;i++){
		int _a = E[i].first;
		int _b = E[i].second;
		if(is[make_pair(_a, _b)]){
			if(ord[make_pair(_a, _b)].first == -1) continue;
			if(ord[make_pair(_a, _b)] != make_pair(_a, _b)){
				ans[i] = 'L';
			} else {
				ans[i] = 'R';
			}
		} else if(is[make_pair(_b, _a)]){
			swap(_a, _b);
			if(ord[make_pair(_a, _b)].first == -1) continue;
			if(ord[make_pair(_a, _b)] != make_pair(_a, _b)){
				ans[i] = 'R';
			} else {
				ans[i] = 'L';
			}
		}
	}
	
	cout << ans;
	
	return 0;
}

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