Submission #47228

#	Time	Username	Problem	Language	Result	Execution time	Memory
47228		robert	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1102 ms	262144 KiB

oneway

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;

vi stck;
vector<vii> g;
vii ed;
string a = "";
vi v;
vi UFDS;
vi usd;

int pt(int n){
	if(UFDS[n]==n)
		return n;
	else
		return UFDS[n] = pt(UFDS[n]);
}

int mrg(int l, int r){
	return UFDS[pt(l)] = pt(r);
}

bool dfs_cycle(int n, int p){
	if(v[n]){
/*		for(int x=0; x<stck.size(); x++){
			if(ed[stck[x]].first==n||ed[stck[x]].second==n){
				if(x!=0)
					x++;
				while(x<stck.size()){
					cout << n << " " << stck[x] << endl;
					a[stck[x]] = 'B';
					x++;
				}
			}
*/		//}
		a[p] = 'B';
		return 1;
	}
	v[n] = 1;
	bool c = 0;
	for(int x=0; x<g[n].size(); x++){
		if(g[n][x].second!=p&&!usd[g[n][x].second]){
			stck.push_back(g[n][x].second);
			usd[g[n][x].second] = 1;
			if(dfs_cycle(g[n][x].first, g[n][x].second)){
				mrg(g[n][x].first, n);
				c = 1;
			}
			usd[g[n][x].second] = 0;
		}
	}
	v[n] = 0;
	return c;
}

bool dfs_path(int n, int d){
	if(v[n])
		return 0;
	if(n==d){
		return 1;
	}
	v[n] = 1;
	bool r = 0;
	for(int x=0; x<g[n].size(); x++){
		if(!v[g[n][x].first]){
			//not visited yet
			if(dfs_path(g[n][x].first, d)){
				//reachable
				if(a[g[n][x].second]=='0'){
					if(ed[g[n][x].second].first==n){
						//from first to second
						a[g[n][x].second] = 'R';
					} else {
						a[g[n][x].second] = 'L';
					}
				}
				r=1;
			}
		}
	}
	//v[n] = 0;
	return r;
}

int main(){
	int N, M, P; cin>>N>>M;
	a = string(M, '0');
	int A, B;
	g.assign(N+1, vii());
	for(int m=0; m<M; m++){
		cin>>A>>B;
		g[A].push_back({B, m});
		g[B].push_back({A, m});
		ed.push_back({A, B});
	}
	UFDS.assign(N+1, 0);
	usd.assign(M+1, 0);
	for(int n=0; n<=N; n++)
		UFDS[n] = n;
	v.assign(N+1, 0);
	for(int n=1; n<=N; n++){
//		v.assign(N+1, 0);
		if(!v[n]){
			dfs_cycle(n, -1);
		}
	}
	cin>>P;
	//cout << a << endl;
	for(int p=0; p<P; p++){
		cin>>A>>B;
		//find path from A to B, changing edges on the way
		v.assign(N+1, 0);
		dfs_path(A, B);
	}
//	cout << a << endl;
	for(int x=0; x<M; x++){
		if(a[x]=='0')
			a[x] = 'B';
	}
	cout << a << endl;
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'bool dfs_cycle(int, int)':
oneway.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0; x<g[n].size(); x++){
               ~^~~~~~~~~~~~
oneway.cpp: In function 'bool dfs_path(int, int)':
oneway.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0; x<g[n].size(); x++){
               ~^~~~~~~~~~~~

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