oj.uz

답안 #379730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379730 2021-03-19T06:10:37 Z errorgorn One-Way Streets (CEOI17_oneway) C++17
100 / 100
 449 ms 66972 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

struct ufds{
	int p[100005];
	int r[100005];
	
	ufds(){
		for (int x=0;x<100005;x++){
			p[x]=x;
			r[x]=0;
		}
	}
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	void unions(int i,int j){
		i=par(i),j=par(j);
		if (i==j) return;
		if (r[i]<r[j]){
			p[i]=j;
		}
		else{
			p[j]=i;
			if (r[i]==r[j]) r[i]++;
		}
	}
} dsu;

int n,m,q;
vector<int> al[100005];
int counter=1;
int in[100005];
int low[100005];
bool vis[100005];
void dfs(int i,int p){
	vis[i]=true;
	in[i]=low[i]=counter++;
	
	bool fp=true;
	for (auto &it:al[i]){
		if (it==p && fp){
			fp=false;
			continue;
		}
		if (in[it]){
			dsu.unions(i,it);
			low[i]=min(low[i],in[it]);
		}
		else{
			dfs(it,i);
			if (low[it]<=in[i]) dsu.unions(i,it);
			low[i]=min(low[i],low[it]);
		}
	}
}

vector<iii> edges;
int component[100005];
vector<ii> tal[100005];
set<int> s[100005];

int ans[100005];

void dfs2(int i,int p){
	vis[i]=true;
	for (auto &it:tal[i]){
		if (it.fi==p) continue;
		
		dfs2(it.fi,i);
		
		int tt=it.se;
		if (tt<0) tt=~tt;
		if (!s[it.fi].empty()){
			int temp=*s[it.fi].begin();
			
			if ((temp<0) != (it.se<0)) ans[tt]=1;
			else ans[tt]=2;
		}
		
		if (sz(s[it.fi])>sz(s[i])) swap(s[i],s[it.fi]);
		
		for (auto &it:s[it.fi]){
			if (s[i].count(~it)) s[i].erase(~it);
			else s[i].insert(it);
		}
	}
	
	//cout<<"debug: "<<i<<endl;
	//for (auto &it:s[i]) cout<<it<<" "; cout<<endl;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m;
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		
		al[a].pub(b);
		al[b].pub(a);
		edges.pub(iii(ii(a,b),x));
	}
	
	memset(vis,false,sizeof(vis));
	rep(x,1,n+1) if (!vis[x]) dfs(x,-1);
	
	rep(x,1,n+1) component[x]=dsu.par(x);
	//rep(x,1,n+1) cout<<component[x]<<" "; cout<<endl;
	
	for (auto &it:edges){
		a=component[it.fi.fi],b=component[it.fi.se];
		if (a!=b){
			tal[a].pub(ii(b,it.se));
			tal[b].pub(ii(a,~it.se));
		}
	}
	
	cin>>q;
	rep(x,0,q){
		cin>>a>>b;
		a=component[a],b=component[b];
		if (a!=b) s[a].insert(x),s[b].insert(~x);
	}
	
	memset(ans,-1,sizeof(ans));
	
	memset(vis,false,sizeof(vis));
	rep(x,1,n+1) if (!vis[component[x]]) dfs2(component[x],-1);
	
	rep(x,0,m){
		if (ans[x]==-1) cout<<"B";
		else if (ans[x]==1) cout<<"R";
		else cout<<"L";
	}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10988 KB Output is correct
2 Correct 8 ms 10988 KB Output is correct
3 Correct 8 ms 11116 KB Output is correct
4 Correct 9 ms 11116 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11116 KB Output is correct
7 Correct 9 ms 11244 KB Output is correct
8 Correct 8 ms 11116 KB Output is correct
9 Correct 8 ms 11116 KB Output is correct
10 Correct 8 ms 11116 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10988 KB Output is correct
2 Correct 8 ms 10988 KB Output is correct
3 Correct 8 ms 11116 KB Output is correct
4 Correct 9 ms 11116 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11116 KB Output is correct
7 Correct 9 ms 11244 KB Output is correct
8 Correct 8 ms 11116 KB Output is correct
9 Correct 8 ms 11116 KB Output is correct
10 Correct 8 ms 11116 KB Output is correct
11 Correct 51 ms 18460 KB Output is correct
12 Correct 59 ms 19996 KB Output is correct
13 Correct 66 ms 21640 KB Output is correct
14 Correct 89 ms 23324 KB Output is correct
15 Correct 97 ms 23876 KB Output is correct
16 Correct 124 ms 24240 KB Output is correct
17 Correct 101 ms 27036 KB Output is correct
18 Correct 111 ms 24220 KB Output is correct
19 Correct 93 ms 29084 KB Output is correct
20 Correct 57 ms 19484 KB Output is correct
21 Correct 65 ms 19132 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10988 KB Output is correct
2 Correct 8 ms 10988 KB Output is correct
3 Correct 8 ms 11116 KB Output is correct
4 Correct 9 ms 11116 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11116 KB Output is correct
7 Correct 9 ms 11244 KB Output is correct
8 Correct 8 ms 11116 KB Output is correct
9 Correct 8 ms 11116 KB Output is correct
10 Correct 8 ms 11116 KB Output is correct
11 Correct 51 ms 18460 KB Output is correct
12 Correct 59 ms 19996 KB Output is correct
13 Correct 66 ms 21640 KB Output is correct
14 Correct 89 ms 23324 KB Output is correct
15 Correct 97 ms 23876 KB Output is correct
16 Correct 124 ms 24240 KB Output is correct
17 Correct 101 ms 27036 KB Output is correct
18 Correct 111 ms 24220 KB Output is correct
19 Correct 93 ms 29084 KB Output is correct
20 Correct 57 ms 19484 KB Output is correct
21 Correct 65 ms 19132 KB Output is correct
22 Correct 360 ms 50076 KB Output is correct
23 Correct 440 ms 64156 KB Output is correct
24 Correct 442 ms 66972 KB Output is correct
25 Correct 337 ms 50204 KB Output is correct
26 Correct 394 ms 49308 KB Output is correct
27 Correct 449 ms 55824 KB Output is correct
28 Correct 45 ms 15772 KB Output is correct
29 Correct 162 ms 29852 KB Output is correct
30 Correct 228 ms 32688 KB Output is correct
31 Correct 97 ms 24220 KB Output is correct
32 Correct 301 ms 38300 KB Output is correct