제출 #659556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659556		jiahng	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	274 ms	41548 KiB

oneway

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

typedef long long ll;
#define ll int
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MOD 1000000007
#define maxn 100010
#define INF (ll)1e18

int TC;
int N,M;
vi adj[maxn];

int low[maxn], disc[maxn], grp[maxn], num = 1;
stack <int> s; bool onstack[maxn]; //disc is discovery time
int ans[maxn], counter = 1;
void dfs(int x, int p) {
	disc[x] = low[x] = counter++;
	s.push(x);
	onstack[x] = true; int co = 0;
	for (auto i: adj[x]) {
		if (i == p){
			co++;
			if (co > 1){
				low[x] = min(low[x],disc[i]);
			}
			continue;
		}
		if (disc[i] == -1) {
			dfs(i,x);
			low[x] = min(low[x],low[i]);
		} else if (onstack[i]) {
			low[x] = min(low[x],disc[i]);
		}
	}
	if (disc[x] == low[x]) {
		int cur;
		while (1) {
			cur = s.top();
			s.pop();
			onstack[cur] = false;
			grp[cur] = num;
			if (cur == x) break;
		}
		num++;
	}
}

int P, X[maxn], Y[maxn];
vpi Z[maxn];

unordered_set <int> st[maxn];
void insert(int i, int x,int y){
	int a = x + y*P, b = x + (!y) * P;
	if (st[i].find(b) != st[i].end()){
		st[i].erase(b); //co[!y]--;
	}else{
		st[i].insert(a); //co[y]++;
	}
}
int ans2[maxn], par[maxn];
bool vis[maxn];
void findans(int x, int p){ //set merging
	int mx = -1; par[x] = p;
	assert(!vis[x]);
	vis[x] = 1;
	aFOR(i,adj[x]) if (i != p){
		findans(i, x);
		if (mx == -1 || st[mx].size() < st[i].size()) mx = i;
	}

	if (mx != -1) st[x].swap(st[mx]);
	aFOR(i,Z[x]) insert(x, i.f, i.s);
	aFOR(i,adj[x]) if (i != p && i != mx){
		aFOR(j, st[i]){
			int z = j; bool y = 0;
			if (j > P){z -= P; y = 1;}
			insert(x, z, y);
		}
		st[i].clear();
	}
	//~ assert(st[x].co[0] == 0 || st[x].co[1] == 0);
	if (st[x].empty()) ans2[x] = 2;
	else if (*st[x].begin() <= P) ans2[x] = 0; // upward
	else ans2[x] = 1; // downward
	//~ else 
	//~ else assert(0);
}
int32_t main() {
    fast;
    mem(ans,-1);
    cin >> N >> M;
    vpi edges;
    int a,b;
    FOR(i,1,M){
		cin >> a >> b; adj[a].pb(b); adj[b].pb(a);
		edges.pb(pi(a,b));
	}
	cin >> P;
	FOR(i,1,P){
		cin >> X[i] >> Y[i];
	}
	
	mem(disc,-1);
	FOR(i,1,N) if (disc[i] == -1) dfs(i,-1);
	
	FOR(i,1,N) adj[i].clear();
	//~ FOR(i,1,N) cout << grp[i] << ' ';
	//~ cout << '\n';
	FOR(i,1,N) vis[i] = 0;
	FOR(i,0,M-1){
		if (grp[edges[i].f] == grp[edges[i].s]){
			ans[i] = 2;
		}else{
			adj[grp[edges[i].f]].pb(grp[edges[i].s]);
			adj[grp[edges[i].s]].pb(grp[edges[i].f]);
		}
	}
	FOR(i,1,P){
		int a = grp[X[i]], b = grp[Y[i]];
		if (a != b){
			Z[a].pb(pi(i, 0)); Z[b].pb(pi(i, 1));
		}
	}
	mem(ans2,-1);
	findans(1,-1);

	FOR(i,1,num-1) if (!vis[i]) findans(i,-1);
	FOR(i,0,M-1){
		int a = grp[edges[i].f], b = grp[edges[i].s];
		if (a != b){
			int x;
			if (par[a] == b) x = a;
			else x = b;
			assert(ans2[x] != -1);
			if (ans2[x] == 2) ans[i] = 2;
			else if (ans2[x] == 0){
				if (x == a){ // a is child, a->b 
					ans[i] = 1;
				}else ans[i] = 0;
			}else{
				if (x == a) ans[i] = 0;
				else ans[i] = 1;
			}
		}
	}
	FOR(i,0,M-1){
		if (ans[i] == 2) cout << 'B';
		else if (ans[i] == 0) cout << 'L';
		else cout << 'R';
	}
}

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