oj.uz

Submission #438581

# Submission time Handle Problem Language Result Execution time Memory
438581 2021-06-28T09:16:46 Z huangqr One-Way Streets (CEOI17_oneway) C++14
100 / 100
 143 ms 24064 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];
				assert((E.a==ha)^(E.b==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];
				assert((E.a==hb)^(E.b==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 6 ms 8268 KB Output is correct
2 Correct 6 ms 8268 KB Output is correct
3 Correct 7 ms 8396 KB Output is correct
4 Correct 6 ms 8396 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 8428 KB Output is correct
8 Correct 7 ms 8396 KB Output is correct
9 Correct 7 ms 8396 KB Output is correct
10 Correct 6 ms 8396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8268 KB Output is correct
2 Correct 6 ms 8268 KB Output is correct
3 Correct 7 ms 8396 KB Output is correct
4 Correct 6 ms 8396 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 8428 KB Output is correct
8 Correct 7 ms 8396 KB Output is correct
9 Correct 7 ms 8396 KB Output is correct
10 Correct 6 ms 8396 KB Output is correct
11 Correct 69 ms 23444 KB Output is correct
12 Correct 75 ms 24064 KB Output is correct
13 Correct 98 ms 22284 KB Output is correct
14 Correct 127 ms 20816 KB Output is correct
15 Correct 106 ms 20680 KB Output is correct
16 Correct 104 ms 17148 KB Output is correct
17 Correct 102 ms 18624 KB Output is correct
18 Correct 129 ms 17152 KB Output is correct
19 Correct 84 ms 19652 KB Output is correct
20 Correct 88 ms 20684 KB Output is correct
21 Correct 68 ms 20152 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8268 KB Output is correct
2 Correct 6 ms 8268 KB Output is correct
3 Correct 7 ms 8396 KB Output is correct
4 Correct 6 ms 8396 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 8428 KB Output is correct
8 Correct 7 ms 8396 KB Output is correct
9 Correct 7 ms 8396 KB Output is correct
10 Correct 6 ms 8396 KB Output is correct
11 Correct 69 ms 23444 KB Output is correct
12 Correct 75 ms 24064 KB Output is correct
13 Correct 98 ms 22284 KB Output is correct
14 Correct 127 ms 20816 KB Output is correct
15 Correct 106 ms 20680 KB Output is correct
16 Correct 104 ms 17148 KB Output is correct
17 Correct 102 ms 18624 KB Output is correct
18 Correct 129 ms 17152 KB Output is correct
19 Correct 84 ms 19652 KB Output is correct
20 Correct 88 ms 20684 KB Output is correct
21 Correct 68 ms 20152 KB Output is correct
22 Correct 143 ms 18548 KB Output is correct
23 Correct 122 ms 17092 KB Output is correct
24 Correct 122 ms 17264 KB Output is correct
25 Correct 106 ms 21440 KB Output is correct
26 Correct 125 ms 18240 KB Output is correct
27 Correct 112 ms 17204 KB Output is correct
28 Correct 51 ms 20512 KB Output is correct
29 Correct 94 ms 20328 KB Output is correct
30 Correct 114 ms 20292 KB Output is correct
31 Correct 104 ms 20552 KB Output is correct
32 Correct 94 ms 21644 KB Output is correct