Submission #1157109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157109		SmuggingSpun	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	46 ms	14784 KiB

oneway

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const int lim = 1e5 + 5;
int n, m, p, a[lim], b[lim], x[lim], y[lim];
namespace sub1{
	void solve(){
		vector<char>ans(m + 1, 'B');
		vector<int>par(n + 1);
		auto find_set = [&] (int N){
			while(N != par[N]){
				N = par[N] = par[par[N]];
			}	
			return N;
		};
		auto merge = [&] (int u, int v){
			par[find_set(u)] = find_set(v);	
		};
		for(int i = 1; i <= m; i++){
			iota(par.begin(), par.end(), 0);
			for(int j = 1; j <= m; j++){
				if(j != i){
					merge(a[j], b[j]);
				}
			}
			for(int j = 1; j <= p; j++){
				int X = find_set(x[j]), Y = find_set(y[j]);
				if(X != Y){
					if(X == find_set(a[i]) && Y == find_set(b[i])){
						ans[i] = 'R';
						break;
					}
					else if(X == find_set(b[i]) && Y == find_set(a[i])){
						ans[i] = 'L';
						break;
					}
				}
			}
		}
		for(int i = 1; i <= m; i++){
			cout << ans[i];
		}
	}
}
namespace sub23{
	char ans[lim];
	int time_dfs = 0, num[lim], low[lim], tail[lim], parent[lim], match[lim], f[lim];
	vector<int>bridge, not_bridge, g[lim];
	bitset<lim>used;
	int find_set(int N){
		return N == parent[N] ? N : parent[N] = find_set(parent[N]);
	}
	void merge(int a, int b){
		parent[find_set(a)] = find_set(b);
	}
	void dfs_1(int s){
		low[s] = num[s] = ++time_dfs;
		for(int& i : g[s]){
			if(!used.test(i)){
				used.set(i);
				int d = a[i] ^ b[i] ^ s;
				if(num[d] == 0){
					dfs_1(d);
					minimize(low[s], low[d]); 
					if(low[d] > num[s]){
						bridge.emplace_back(i);
					}
					else{
						not_bridge.emplace_back(i);
					}
				}
				else{
					minimize(low[s], num[d]);
					not_bridge.emplace_back(i);
				}
			}
		}
	}
	void dfs_2(int s){
		low[s] = ++time_dfs;
		for(int& i : g[s]){
			int d = a[i] ^ b[i] ^ s;
			if(low[d] == 0){
				match[d] = i;
				dfs_2(d);
			}	
		}
	}
	void dfs_3(int s, int p = -1){
		for(int& i : g[s]){
			int d = a[i] ^ b[i] ^ s;
			if(d != p){
				dfs_3(d, s);
				f[s] += f[d];
			}
		}
		int i = match[s];
		if(f[s] > 0){
			ans[i] = (low[a[i]] < low[b[i]] ? 'R' : 'L');
		}
		else if(f[s] < 0){
			ans[i] = (low[a[i]]< low[b[i]] ? 'L' : 'R');
		}
	}
	void solve(){
		fill(ans + 1, ans + m + 1, 'B');
		for(int i = 1; i <= m; i++){
			g[a[i]].emplace_back(i);
			g[b[i]].emplace_back(i);
		}
		used.reset();
		memset(num, 0, sizeof(num));
		for(int i = 1; i <= n; i++){
			if(num[i] == 0){
				dfs_1(i);
			}
		}
		iota(parent + 1, parent + n + 1, 1);
		for(int& i : not_bridge){
			merge(a[i], b[i]);
		}
		for(int i = 1; i <= n; i++){
			g[i].clear();
		}
		for(int& i : bridge){
			g[a[i] = find_set(a[i])].emplace_back(i);
			g[b[i] = find_set(b[i])].emplace_back(i);
		}
		memset(low, time_dfs = 0, sizeof(low));
		vector<int>root;
		for(int i = 1; i <= n; i++){
			if(i == find_set(i) && low[i] == 0){
				match[i] = 0;
				dfs_2(i);
				root.emplace_back(i);
			}
		}
		memset(f, 0, sizeof(f));
		for(int i = 1; i <= p; i++){
			f[find_set(y[i])]++;
			f[find_set(x[i])]--;
		}
		for(int& i : root){
			dfs_3(i);
		}
		for(int i = 1; i <= m; i++){
			cout << ans[i];
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i];
	}
	cin >> p;
	for(int i = 1; i <= p; i++){
		cin >> x[i] >> y[i];
	}
	if(max(n, m) <= 1000 && p <= 100){
		sub23::solve();
	}
	else{
		sub23::solve();
	}
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:159:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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