Submission #1204480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204480		PlayVoltz	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	302 ms	61100 KiB

oneway

#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

struct trio{
	int a, b, c;
};

int counter=0;
vector<vector<trio> > graph;
vector<int> low, disc, ans, in, out, l, r;
vector<set<int> > s;

void dfs(int node, int par, int d){
	disc[node]=low[node]=d;
	in[node]=++counter;
	for (auto [i, j, dir]:graph[node]){
		if (j==par)continue;
		if (disc[i])low[node]=min(low[node], disc[i]);
		else{
			dfs(i, j, d+1);
			low[node]=min(low[node], low[i]);
			if (low[i]>=disc[i]&&!s[i].empty()){
				int c=*s[i].begin();
				if (in[i]<=in[l[c]]&&out[i]>=out[l[c]])ans[j]=dir;
				else ans[j]=(dir==1?2:1);
			}
			if (s[i].size()>s[node].size())swap(s[i], s[node]);
			for (auto a:s[i]){
				if (s[node].find(a)==s[node].end())s[node].insert(a);
				else s[node].erase(a);
			}
		} 
	}
	out[node]=counter;
}

int32_t main(){
	int n, m, q, a, b;
	cin>>n>>m;
	graph.resize(n+1);
	low.resize(n+1);
	disc.resize(n+1, 0);
	ans.resize(m, 0);
	in.resize(n+1);
	out.resize(n+1);
	s.resize(n+1);
	for (int i=0; i<m; ++i){
		cin>>a>>b;
		graph[a].pb({b, i, 1});
		graph[b].pb({a, i, 2});
	}
	cin>>q;
	l.resize(q);
	r.resize(q);
	for(int i=0; i<q; ++i){
		cin>>a>>b;
		if (a==b)continue;
		s[a].insert(i);
		s[b].insert(i);
		l[i]=a, r[i]=b;
	}
	for (int i=1; i<=n; ++i)if (!disc[i])dfs(i, -1, 1);
	for (int i=0; i<m; ++i){
		if (!ans[i])cout<<'B';
		else if (ans[i]==1)cout<<'L';
		else cout<<'R';
	}
}

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