Submission #791010

#	Time	Username	Problem	Language	Result	Execution time	Memory
791010		phoenix0423	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	75 ms	22792 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
typedef pair<pll, ll> tll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 1e5 + 5;
vector<pll> adj[maxn];
int in[maxn], low[maxn], id[maxn], cnt[maxn], dfn = 1;
int n, m, gp = 0;
stack<int> stk;
void dfs(int pos, int idx){
	in[pos] = low[pos] = dfn++;
	stk.push(pos);
	for(auto [x, index] : adj[pos]){
		if(index % m == idx % m) continue;
		if(!in[x]) dfs(x, index);
		low[pos] = min(low[pos], low[x]);
	}
	if(in[pos] == low[pos]){
		while(stk.top() != pos){
			int x = stk.top(); stk.pop();
			id[x] = gp;
		}
		stk.pop();
		id[pos] = gp;
		gp++;
	}
}
string key = "RLB";
vector<pll> nadj[maxn];
int ncnt[maxn], ans[maxn], vis[maxn];
void build_new_graph(){
	for(int i = 0; i < n; i++){
		ncnt[id[i]] += cnt[i];
		for(auto [x, idx] : adj[i]){
			if(id[x] == id[i]){
				ans[idx % m] = 2;
			}
			else nadj[id[i]].eb(id[x], idx);
		}
	}
}
void dfsans(int pos, int prev){
	vis[pos] = 1;
	for(auto [x, idx] : nadj[pos]){
		if(idx % m == prev % m) continue;
		dfsans(x, idx);
		if(ncnt[x] > 0) ans[idx % m] = (idx < m ? 1 : 0);
		else if(ncnt[x] < 0) ans[idx % m] = (idx < m ? 0 : 1);
		else ans[idx % m] = 2;
		ncnt[pos] += ncnt[x];
	}
}
void solve(){
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int a, b;
		cin>>a>>b;
		a--, b--;
		adj[a].eb(b, i);
		adj[b].eb(a, i + m);
	}
	int p;
	cin>>p;
	for(int i = 0; i < p; i++){
		int a, b;
		cin>>a>>b;
		a--, b--;
		cnt[a] ++, cnt[b] --;
	}
	//generate a cut-block-tree
	for(int i = 0; i < n; i++){
		if(!in[i]) dfs(i, -1);
	}
	build_new_graph();
	for(int i = 0; i < gp; i++){
		if(!vis[i]) dfsans(i, -1);
	}
	for(int i = 0; i < m; i++) cout<<key[ans[i]];
}
int main(void){
	fastio;
	int t = 1;
	// cin>>t;
	while(t--){
		solve();
	}
}

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