Submission #878675

#	Time	Username	Problem	Language	Result	Execution time	Memory
878675		UmairAhmadMirza	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	348 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
int const N=1e3+5;
vector<int> adj[N];
int n,m;
bool vis1[N];
bool inpath[N];
int cnt[N];
map<pair<int,int>,int> mp;
void dfs1(int node,int par){
	// cout<<node<<endl;
	vis1[node]=1;
	inpath[node]=1;
	bool p=1;
	for(auto i:adj[node]){
		if(vis1[i]==0){
			dfs1(i,node);
			cnt[node]+=cnt[i];
			if(cnt[i]>0){
				mp[{i,node}]='B';
				mp[{node,i}]='B';
			}
		}
		if(i==par&&p==1)
			p=0;
		else if(inpath[i]){
			cnt[node]++;
			cnt[i]--;
			mp[{node,i}]='B';
			mp[{i,node}]='B';
		}
	}
	inpath[node]=0;
}
vector<int> path;
int des=0;
bool vis[N];
void dfs(int node){
	path.push_back(node);
	vis[node]=1;
	if(node==des){
		des=-1;
		int sz=path.size();
		for(int i=0;i<sz-1;i++){
			if(mp[{path[i],path[i+1]}]!='B')
				mp[{path[i],path[i+1]}]='D';
		}
	}
	if(des==-1)
		return;
	for(auto i:adj[node]){
		if(vis[i]==0)
			dfs(i);
	}
	path.pop_back();
}
int main(){
	cin>>n>>m;
	if(n>1000){
		cout<<"!"<<endl;
		return 0;
	}
	vector<pair<int,int>> edge;
	for (int i = 0; i < m; ++i){
		int u,v;
		cin>>u>>v;
		edge.push_back({u,v});
		if(u==v)
			continue;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs1(1,0);
	int k;
	cin>>k;
	pair<int,int> sp[k];
	for (int i = 0; i < k; ++i){
		cin>>sp[i].first>>sp[i].second;
		des=sp[i].second;
		dfs(sp[i].first);
		for(int i=0;i<=n;i++)
			vis[i]=0;
		path.clear();
	}
	for(auto ed:edge){
		int u=ed.first;
		int v=ed.second;
		if(mp[ed]=='D')
			cout<<'R';
		else if(mp[{v,u}]=='D')
			cout<<'L';
		else
			cout<<'B';
	}
	cout<<endl;
	return 0;
}

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