oj.uz

Submission #438580

# Submission time Handle Problem Language Result Execution time Memory
438580 2021-06-28T09:16:11 Z huangqr One-Way Streets (CEOI17_oneway) C++14
100 / 100
 175 ms 25116 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const ll lim=1e5+5;
ll n,m,q;
vector<char>ans;

struct UFDS{
	ll par[lim];
	UFDS(){
		for(int i=0;i<lim;i++)par[i]=i;
	}
	ll findset(ll pos){
		if(pos==par[pos])return pos;
		else return par[pos]=findset(par[pos]);
	}
	void mergeset(ll a,ll b){
		a = findset(a),b = findset(b);
		if(a!=b)par[b]=a;
	}
}ufds;

struct Edge{
	ll x,a,b,idx;//x is the other guy, a and b are original order of edge
	Edge(ll xx,ll aa,ll bb,ll ii){
		x=xx,a=aa,b=bb,idx=ii;
	}
	Edge(){}
};

struct Graph{
	vector<Edge>adjl[lim],nontree;
	ll par[lim],depth[lim];
	Edge paredge[lim];
	bool vis[lim],root[lim];
	Graph(){
		fill(vis,vis+lim,0);
		fill(root,root+lim,0);
		fill(depth,depth+lim,0);
		par[1]=1;
		depth[1]=0;
	}
	void dfs(ll pos,ll pre_idx){
		vis[pos]=1;
		//cout<<"pos:"<<pos<<"\n";
		for(Edge &E:adjl[pos]){
			if(E.idx==pre_idx){
				swap(E,adjl[pos].back());
				adjl[pos].pop_back();
				break;
			}
		}
		for(Edge E:adjl[pos]){
			if(!vis[E.x]){
				vis[E.x]=1;
				par[E.x]=pos;
				paredge[E.x]=E;
				depth[E.x]=depth[pos]+1;
				dfs(E.x,E.idx);
			}
			else if(pos<E.x){ //prevent duplication (each extra edge goes into nontree once only)
		//		cout<<"pos eidx:"<<pos<<" "<<E.idx<<"\n";
				nontree.push_back(E);
			}
		}
		return;
	}
	void roottrees(){
		for(int i=1;i<=n;i++){
			if(vis[i]==0)dfs(i,-1),root[i]=1;
		}
	}
	
	//Part 1, processing the nontree edges
	void proc(Edge E){//marks a cycle in the tree
		ll ha=ufds.findset(E.a),hb=ufds.findset(E.b);
		while(ha!=hb){
			if(depth[ha]<depth[hb])swap(ha,hb);
			ufds.mergeset(par[ha],ha);
			ans[paredge[ha].idx]='B';
			ha=ufds.findset(par[ha]);
		}
		return;
	}
	void genH(){
		for(auto E:nontree){
			ans[E.idx]='B';
			proc(E);
		}
		return;
		for(int i=1;i<=n;i++){
			if(root[i]){
	//			cout<<i<<" is a root\n";
				continue;
			}
			if(ufds.findset(i)==i){
		//		cout<<i<<" is a head\n";
	//			H->adjl[ufds.findset(par[i])].push_back(paredge[i]);
//				cout<<ufds.findset(par[i])<<" "<<(i)<<"\n";
//				cout<<"Edge:"<<paredge[i].a<<" "<<paredge[i].b<<"\n\n";
			}
		}
		return;
	}
	
	//Part 2, answering the queries
	void query(ll a,ll b){
		ll ha=ufds.findset(a),hb=ufds.findset(b);
		while(ha!=hb){
			if(depth[ha]>depth[hb]){
				ll nxt=ufds.findset(par[ha]);
				ufds.mergeset(nxt,ha);
				Edge E=paredge[ha];
				ans[E.idx]= (E.a==ha)?'R':'L';
				ha=nxt;
			}
			else{
				ll nxt=ufds.findset(par[hb]);
				ufds.mergeset(nxt,hb);
				Edge E=paredge[hb];
				ans[E.idx]= (E.a==hb)?'L':'R';
				hb=nxt;
			}
		}
		return;
	}
};

int main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL);
	cin>>n>>m;
	ans=vector<char>(m,'B');
	Graph G;
	for(int i=0;i<m;i++){
		ll a,b;
		cin>>a>>b;
		if(a==b){
			ans[i]='B';
			continue;
		}
		G.adjl[a].push_back(Edge(b,a,b,i));
		G.adjl[b].push_back(Edge(a,a,b,i));
	}
	G.roottrees();
	G.genH();
	cin>>q;
	while(q--){
		ll a,b;
		cin>>a>>b;
		G.query(a,b);
	}
//	for(auto x:G.nontree){
//		cout<<x.a<<" "<<x.b<<" "<<x.idx<<"\n";
//	}
	for(auto c:ans)cout<<c;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8268 KB Output is correct
2 Correct 6 ms 8328 KB Output is correct
3 Correct 7 ms 8460 KB Output is correct
4 Correct 7 ms 8344 KB Output is correct
5 Correct 6 ms 8396 KB Output is correct
6 Correct 7 ms 8396 KB Output is correct
7 Correct 6 ms 8324 KB Output is correct
8 Correct 6 ms 8392 KB Output is correct
9 Correct 6 ms 8456 KB Output is correct
10 Correct 7 ms 8472 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8268 KB Output is correct
2 Correct 6 ms 8328 KB Output is correct
3 Correct 7 ms 8460 KB Output is correct
4 Correct 7 ms 8344 KB Output is correct
5 Correct 6 ms 8396 KB Output is correct
6 Correct 7 ms 8396 KB Output is correct
7 Correct 6 ms 8324 KB Output is correct
8 Correct 6 ms 8392 KB Output is correct
9 Correct 6 ms 8456 KB Output is correct
10 Correct 7 ms 8472 KB Output is correct
11 Correct 76 ms 24584 KB Output is correct
12 Correct 76 ms 25116 KB Output is correct
13 Correct 91 ms 23432 KB Output is correct
14 Correct 126 ms 22084 KB Output is correct
15 Correct 116 ms 21828 KB Output is correct
16 Correct 100 ms 18268 KB Output is correct
17 Correct 95 ms 19780 KB Output is correct
18 Correct 104 ms 18328 KB Output is correct
19 Correct 97 ms 20804 KB Output is correct
20 Correct 83 ms 21896 KB Output is correct
21 Correct 69 ms 21292 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8268 KB Output is correct
2 Correct 6 ms 8328 KB Output is correct
3 Correct 7 ms 8460 KB Output is correct
4 Correct 7 ms 8344 KB Output is correct
5 Correct 6 ms 8396 KB Output is correct
6 Correct 7 ms 8396 KB Output is correct
7 Correct 6 ms 8324 KB Output is correct
8 Correct 6 ms 8392 KB Output is correct
9 Correct 6 ms 8456 KB Output is correct
10 Correct 7 ms 8472 KB Output is correct
11 Correct 76 ms 24584 KB Output is correct
12 Correct 76 ms 25116 KB Output is correct
13 Correct 91 ms 23432 KB Output is correct
14 Correct 126 ms 22084 KB Output is correct
15 Correct 116 ms 21828 KB Output is correct
16 Correct 100 ms 18268 KB Output is correct
17 Correct 95 ms 19780 KB Output is correct
18 Correct 104 ms 18328 KB Output is correct
19 Correct 97 ms 20804 KB Output is correct
20 Correct 83 ms 21896 KB Output is correct
21 Correct 69 ms 21292 KB Output is correct
22 Correct 118 ms 20820 KB Output is correct
23 Correct 123 ms 19396 KB Output is correct
24 Correct 175 ms 19464 KB Output is correct
25 Correct 111 ms 23756 KB Output is correct
26 Correct 126 ms 20608 KB Output is correct
27 Correct 127 ms 19548 KB Output is correct
28 Correct 53 ms 21172 KB Output is correct
29 Correct 90 ms 22200 KB Output is correct
30 Correct 96 ms 22100 KB Output is correct
31 Correct 125 ms 22464 KB Output is correct
32 Correct 96 ms 22996 KB Output is correct