제출 #463510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
463510		vanic	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3 ms	5708 KiB

oneway

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;

const int maxn=1e5+5;

struct union_find{
	int parent[maxn];
	int sz[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
			sz[i]=1;
		}
	}
	int find(int x){
		if(parent[x]==x){
			return x;
		}
		return parent[x]=find(parent[x]);
	}
	void update(int x, int y){
		x=find(x);
		y=find(y);
		if(sz[x]>sz[y]){
			swap(x, y);
		}
		parent[x]=y;
		sz[y]+=sz[x];
	}
	bool query(int x, int y){
		return find(x)==find(y);
	}
};


union_find U;
vector < array < int, 3 > > ms[maxn];
vector < array < int, 4 > > most;

int sol[maxn];
bool bio[maxn];
int disc[maxn];
int mini[maxn];

void dfs(int x, int prosl){
	bio[x]=1;
	if(prosl==x){
		disc[x]=0;
	}
	else{
		disc[x]=disc[prosl]+1;
	}
	bool p=0;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!p && ms[x][i][0]==prosl){
			p=1;
		}
		else if(bio[ms[x][i][0]]){
			disc[x]=min(disc[x], disc[ms[x][i][0]]);
		}
	}
	mini[x]=disc[x];
	int y;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!bio[ms[x][i][0]]){
			y=ms[x][i][0];
			dfs(y, x);
			if(disc[x]<mini[y]){
				most.push_back({x, y, ms[x][i][1], ms[x][i][2]});
			}
			else{
				if(!U.query(x, y)){
					U.update(x, y);
				}
				mini[x]=min(mini[x], mini[y]);
			}
		}
	}
}

vector < array < int, 3 > > novi[maxn];
int val[maxn];


int dfs1(int x, int prosl, int edge, bool p){
	int sum=val[x];
	for(int i=0; i<(int)novi[x].size(); i++){
		if(prosl!=novi[x][i][0]){
			sum+=dfs1(novi[x][i][0], x, novi[x][i][1], novi[x][i][2]^1);
		}
	}
	if(sum>0){
		if(p){
			sol[edge]=1;
		}
		else{
			sol[edge]=-1;
		}
	}
	else if(sum<0){
		if(p){
			sol[edge]=-1;
		}
		else{
			sol[edge]=1;
		}
	}
	return sum;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	int a, b;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back({b, i, 1});
		ms[b].push_back({a, i, 0});
	}
	for(int i=0; i<n; i++){
		if(!bio[i]){
			dfs(i, i);
		}
	}
/*	for(int i=0; i<(int)most.size(); i++){
		cout << most[i][0] << ' ' << most[i][1] << endl;
	}
	for(int i=0; i<n; i++){
		cout << disc[i] << ' ';
	}
	cout << endl;*/
	for(int i=0; i<(int)most.size(); i++){
		novi[U.find(most[i][0])].push_back({U.find(most[i][1]), most[i][2], most[i][3]});
		novi[U.find(most[i][1])].push_back({U.find(most[i][0]), most[i][2], most[i][3]^1});
	}
	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		cin >> a >> b;
		a--;
		b--;
		a=U.find(a);
		b=U.find(b);
		val[a]++;
		val[b]--;
	}
	dfs1(U.find(0), -1, m, 0);
	for(int i=0; i<m; i++){
		if(!sol[i]){
			cout << "B";
		}
		else if(sol[i]==1){
			cout << "R";
		}
		else{
			cout << "L";
		}
	}
	cout << '\n';
	return 0;
}

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