/**
* Notes during contest.
*
* ------ A ------
* Looks like that it's about strongly-connected components, cycles or bridges. I
* think we can detect all cycles and merge all those nodes into one. The resulting
* graph would be a tree, so we can then use a difference array to find each edge's
* direction. Note that any edge in a cycle is B, and any edge not in cycles is a
* "bridge".
* !IMPORTANT! (Reminded by tinjyu during contest) !IMPORTANT!
* Graph may not be CONNECTED.
*
* ------ B ------
* We iterate through all cost k. We can take at most k bets. If we can guarantee
* a profit of p, min(#A_is_the_outcome, #B_is_the_outcome) >= p + k. Binary search
* is ok.
* For each k, we wanna find the max achievable for
* min(#A_is_outcome, #B_is_outcome) - k.
*
* ------ C ------
*
* Time Complexity 1: O(m^2)
* Time Complexity 2: O(n * log(n * VAL_MAX) * log(n))
* Time Complexity 3: O()
* Implementation 0.5 (test if my solution is correct, not optimized, slow)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
const int_t INF = 0x3f3f3f3f3f3f;
// a DSU impl that allows assigning a value to each set
struct DSU {
vec set, rank;
int_t components;
DSU(int_t n) {
set.resize(n);
rank.resize(n);
for (int_t k = 0; k < n; k++)
set[k] = k, rank[k] = 1;
components = n;
}
inline int_t find(int_t k) {
if (set[k] == k)
return k;
return set[k] = find(set[k]);
}
bool merge(int_t a, int_t b) { // merge b into a (keep a's value)
a = find(a), b = find(b);
if (a == b)
return false;
if (rank[b] > rank[a])
std::swap(a, b);
set[b] = a, rank[a] += rank[b], components--;
return true;
}
};
struct edge_t {
int_t a, b;
};
struct neighb_t {
int_t neighb, edge_idx;
};
typedef std::vector<neighb_t> adj_list_t;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int_t n, m;
std::cin >> n >> m;
if (n > 3000) {
std::cout << "bye" << std::endl;
return 0;
}
std::vector<edge_t> original_graph(m);
for (int_t k = 0; k < m; k++) {
std::cin >> original_graph[k].a >> original_graph[k].b;
original_graph[k].a--, original_graph[k].b--;
}
// TODO: improve bridge finding
std::vector<bool> is_bridge(m);
// std::cerr << "[debug] is_bridge[]: ";
for (int_t k = 0; k < m; k++) {
DSU dsu(n);
for (int_t i = 0; i < m; i++) {
if (i == k)
continue;
dsu.merge(original_graph[i].a, original_graph[i].b);
}
int_t c = dsu.components;
dsu.merge(original_graph[k].a, original_graph[k].b);
assert(0 <= c - dsu.components && c - dsu.components <= 1);
is_bridge[k] = (c != dsu.components);
// std::cerr << is_bridge[k];
}
// std::cerr << std::endl;
DSU compress(n); // used to compress the nodes
for (int_t k = 0; k < m; k++) {
if (!is_bridge[k])
compress.merge(original_graph[k].a, original_graph[k].b);
}
vec map(n, -1); // mapping an original node into one in our new graph
// std::cerr << "[debug] map[]: ";
for (int_t k = 0, new_graph_top = 0; k < n; k++) {
if (map[compress.find(k)] == -1)
map[compress.find(k)] = new_graph_top++;
map[k] = map[compress.find(k)];
// std::cerr << map[k] << ' ';
}
// std::cerr << std::endl;
std::vector<adj_list_t> graph(compress.components);
for (int_t k = 0; k < m; k++) {
int_t a = map[original_graph[k].a], b = map[original_graph[k].b];
if (a != b) {
graph[a].push_back(neighb_t{b, k});
graph[b].push_back(neighb_t{a, k});
}
}
n = compress.components;
int_t pairs;
std::cin >> pairs;
vec start(m, -1); // for each edge, if it's a -> b, start[] = a.
// std::cerr << "[debug] requirements:" << std::endl;
for (int_t k = 0; k < pairs; k++) {
int_t src, dst;
std::cin >> src >> dst;
src = map[src - 1], dst = map[dst - 1];
// std::cerr << src << ' ' << dst << std::endl;
if (src == dst)
continue;
// TODO: improve BFS
std::queue<int_t> bfs_queue;
std::vector<int_t> edge_num(n, -1), prev(n, -1);
edge_num[src] = INF; // doesn't exist. Anything not -1 would be good
bfs_queue.emplace(src);
while (!bfs_queue.empty()) {
int_t t = bfs_queue.front();
bfs_queue.pop();
if (t == dst)
break;
for (const neighb_t& e : graph[t]) {
if (edge_num[e.neighb] != -1)
continue;
edge_num[e.neighb] = e.edge_idx, prev[e.neighb] = t;
bfs_queue.push(e.neighb);
}
}
for (int_t pt = dst; pt != src; pt = prev[pt]) {
assert(edge_num[pt] != -1);
start[edge_num[pt]] = prev[pt];
}
}
std::string ans(m, '@');
for (int_t k = 0; k < m; k++) {
if (is_bridge[k]) {
if (start[k] != -1) {
if (map[original_graph[k].a] == start[k])
ans[k] = 'R';
else
ans[k] = 'L';
} else {
ans[k] = 'B';
}
} else {
ans[k] = 'B';
}
}
std::cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
11 ms |
324 KB |
Output is correct |
| 4 |
Correct |
10 ms |
340 KB |
Output is correct |
| 5 |
Correct |
13 ms |
364 KB |
Output is correct |
| 6 |
Correct |
7 ms |
340 KB |
Output is correct |
| 7 |
Correct |
14 ms |
352 KB |
Output is correct |
| 8 |
Correct |
13 ms |
468 KB |
Output is correct |
| 9 |
Correct |
9 ms |
348 KB |
Output is correct |
| 10 |
Correct |
7 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
11 ms |
324 KB |
Output is correct |
| 4 |
Correct |
10 ms |
340 KB |
Output is correct |
| 5 |
Correct |
13 ms |
364 KB |
Output is correct |
| 6 |
Correct |
7 ms |
340 KB |
Output is correct |
| 7 |
Correct |
14 ms |
352 KB |
Output is correct |
| 8 |
Correct |
13 ms |
468 KB |
Output is correct |
| 9 |
Correct |
9 ms |
348 KB |
Output is correct |
| 10 |
Correct |
7 ms |
320 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
11 ms |
324 KB |
Output is correct |
| 4 |
Correct |
10 ms |
340 KB |
Output is correct |
| 5 |
Correct |
13 ms |
364 KB |
Output is correct |
| 6 |
Correct |
7 ms |
340 KB |
Output is correct |
| 7 |
Correct |
14 ms |
352 KB |
Output is correct |
| 8 |
Correct |
13 ms |
468 KB |
Output is correct |
| 9 |
Correct |
9 ms |
348 KB |
Output is correct |
| 10 |
Correct |
7 ms |
320 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
