Submission #644222

#	Time	Username	Problem	Language	Result	Execution time	Memory
644222		ymm	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3070 ms	32720 KiB

oneway

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;

enum {IN, OUT};
enum {UP = 1, DOWN = 2};

class s2l
{
private:
	multiset<pii> s[2];
public:
	size_t size()
	{
		return s[0].size() + s[1].size();
	}
	void insert(int v, int u, bool dir)
	{
		auto it = s[!dir].find({u, v});
		if (it != s[!dir].end())
			s[!dir].erase(it);
		else
			s[dir].insert({v, u});
	}
	void merge(s2l *x)
	{
		if (size() > x->size()) {
			s[IN].swap(x->s[IN]);
			s[OUT].swap(x->s[OUT]);
		}
		for (auto [v, u] : x->s[IN])
			insert(v, u, IN);
		for (auto [v, u] : x->s[OUT])
			insert(v, u, OUT);
		delete(x);
	}
	int get()
	{
		return (DOWN & -s[OUT].empty()) | (UP & -s[IN].empty());
	}
};

vector<pii> Ao[N];
vector<pii> A2[N];
int col2[N];
bool ncut[N];
int h[N];

bool find_ncut_vis[N];
int find_ncut(int v, int p, int h)
{
	::h[v] = h;
	int mn = h;
	find_ncut_vis[v] = 1;
	for (auto [u, ei] : Ao[v]) {
		if (ei == p)
			continue;
		if (find_ncut_vis[u]) {
			mn = min(mn, ::h[u]);
			ncut[ei] = 1;
		} else {
			int x = find_ncut(u, ei, h+1);
			if (x <= h)
				ncut[ei] = 1;
			mn = min(mn, x);
		}
	}
	return mn;
}

void make_col2(int v, int col)
{
	col2[v] = col;
	for (auto [u, ei] : Ao[v]) {
		if (ncut[ei] && col2[u] == -1)
			make_col2(u, col);
	}
}

vector<pii> Eo;
vector<pii> req2[N];

void make_A2()
{
	Loop (i,0,Eo.size()) {
		auto [v, u] = Eo[i];
		v = col2[v];
		u = col2[u];
		if (v != u) {
			A2[v].push_back({u, i});
			A2[u].push_back({v, i});
		}
	}
}

void read_and_make_req2()
{
	int p;
	cin >> p;
	Loop (i,0,p) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		v = col2[v]; u = col2[u];
		if (v != u) {
			req2[v].push_back({u, OUT});
			req2[u].push_back({v, IN});
		}
	}
}

pii ans2[N];

bool main_dfs_vis[N];
s2l *main_dfs(int v, int p)
{
	main_dfs_vis[v] = 1;
	s2l *obj = new s2l;
	for (auto [u, dir] : req2[v])
		obj->insert(v, u, dir);
	for (auto [u, ei] : A2[v]) {
		if (ei == p)
			continue;
		obj->merge(main_dfs(u, ei));
	}
	if (p != -1)
		ans2[p] = {obj->get(), v};
	return obj;
}

char get_char(int ei)
{
	auto [v, u] = Eo[ei];
	switch (ans2[ei].first) {
	case UP|DOWN: return 'B';
	case UP     : return ans2[ei].second == col2[u]? 'L': 'R';
	case    DOWN: return ans2[ei].second == col2[u]? 'R': 'L';
	default     : return 'N';
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	Loop (i,0,m) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		Ao[v].push_back({u,i});
		Ao[u].push_back({v,i});
		Eo.push_back({v, u});
	}
	Loop (i,0,n)
		if (!find_ncut_vis[i])
			find_ncut(i, -1, 0);
	//Loop (i,0,m) cout << ncut[i] << ' '; cout << '\n';
	int n2 = 0;
	memset(col2, -1, sizeof(col2));
	Loop (i,0,n) {
		if (col2[i] == -1)
			make_col2(i, n2++);
	}
	//Loop (i,0,n) cout << col2[i] << ' '; cout << '\n';
	make_A2();
	read_and_make_req2();
	Loop (i,0,n2)
		if (!main_dfs_vis[i])
			delete(main_dfs(i, -1));
	Loop (i,0,m) {
		auto [v, u] = Eo[i];
		cout << (col2[v] == col2[u]? 'B': get_char(i));
	}
	cout << '\n';
}

Compilation message (stderr)

oneway.cpp: In function 'void make_A2()':
oneway.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
oneway.cpp:91:2: note: in expansion of macro 'Loop'
   91 |  Loop (i,0,Eo.size()) {
      |  ^~~~

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