oj.uz

Submission #644225

# Submission time Handle Problem Language Result Execution time Memory
644225 2022-09-24T05:54:10 Z ymm One-Way Streets (CEOI17_oneway) C++17
100 / 100
 295 ms 44284 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7764 KB Output is correct
2 Correct 5 ms 7784 KB Output is correct
3 Correct 5 ms 7764 KB Output is correct
4 Correct 6 ms 7764 KB Output is correct
5 Correct 5 ms 7892 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7892 KB Output is correct
8 Correct 5 ms 7892 KB Output is correct
9 Correct 4 ms 7764 KB Output is correct
10 Correct 5 ms 7764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7764 KB Output is correct
2 Correct 5 ms 7784 KB Output is correct
3 Correct 5 ms 7764 KB Output is correct
4 Correct 6 ms 7764 KB Output is correct
5 Correct 5 ms 7892 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7892 KB Output is correct
8 Correct 5 ms 7892 KB Output is correct
9 Correct 4 ms 7764 KB Output is correct
10 Correct 5 ms 7764 KB Output is correct
11 Correct 38 ms 12488 KB Output is correct
12 Correct 42 ms 13760 KB Output is correct
13 Correct 47 ms 14796 KB Output is correct
14 Correct 56 ms 15764 KB Output is correct
15 Correct 70 ms 16256 KB Output is correct
16 Correct 89 ms 17468 KB Output is correct
17 Correct 82 ms 22532 KB Output is correct
18 Correct 78 ms 17620 KB Output is correct
19 Correct 71 ms 26280 KB Output is correct
20 Correct 39 ms 12712 KB Output is correct
21 Correct 37 ms 13376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7764 KB Output is correct
2 Correct 5 ms 7784 KB Output is correct
3 Correct 5 ms 7764 KB Output is correct
4 Correct 6 ms 7764 KB Output is correct
5 Correct 5 ms 7892 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7892 KB Output is correct
8 Correct 5 ms 7892 KB Output is correct
9 Correct 4 ms 7764 KB Output is correct
10 Correct 5 ms 7764 KB Output is correct
11 Correct 38 ms 12488 KB Output is correct
12 Correct 42 ms 13760 KB Output is correct
13 Correct 47 ms 14796 KB Output is correct
14 Correct 56 ms 15764 KB Output is correct
15 Correct 70 ms 16256 KB Output is correct
16 Correct 89 ms 17468 KB Output is correct
17 Correct 82 ms 22532 KB Output is correct
18 Correct 78 ms 17620 KB Output is correct
19 Correct 71 ms 26280 KB Output is correct
20 Correct 39 ms 12712 KB Output is correct
21 Correct 37 ms 13376 KB Output is correct
22 Correct 242 ms 33348 KB Output is correct
23 Correct 294 ms 29188 KB Output is correct
24 Correct 295 ms 27764 KB Output is correct
25 Correct 208 ms 44284 KB Output is correct
26 Correct 209 ms 31936 KB Output is correct
27 Correct 247 ms 28520 KB Output is correct
28 Correct 38 ms 10772 KB Output is correct
29 Correct 107 ms 22164 KB Output is correct
30 Correct 124 ms 23772 KB Output is correct
31 Correct 70 ms 17084 KB Output is correct
32 Correct 188 ms 31860 KB Output is correct