Submission #47226

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

oneway

#include <iostream>
#include <vector>

using namespace std;

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

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

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

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

bool dfs_cycle(int n, int p){
	if(v[n])
		return 1;
	v[n] = 1;
	bool c = 0;
	for(int x=0; x<g[n].size(); x++){
		if(g[n][x].second!=p){
			if(dfs_cycle(g[n][x].first, g[n][x].second)){
				mrg(g[n][x].first, n);
				a[g[n][x].second] = 'B';
				c = 1;
			}
		}
	}
	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);
	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);
	}
	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 'int mrg(int, int)':
oneway.cpp:25:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
oneway.cpp: In function 'bool dfs_cycle(int, int)':
oneway.cpp:32: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:52: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