#include <bits/stdc++.h>
using namespace std;
int dfs(int x, int p, int id, vector<vector<pair<int, int>>> &AR, int &buff, vector<int> &ordre, vector<int> &low, vector<int> &incycle, vector<int> ¬cycle)
{
if (low[x] != low.size())
{
incycle.push_back(id);
return low[x];
}
ordre[x] = buff;
low[x] = buff++;
for (int i = 0; i < AR[x].size(); i++)
{
if (AR[x][i].first == p)
continue;
low[x] = min(low[x], dfs(AR[x][i].first, x, AR[x][i].second, AR, buff, ordre, low, incycle, notcycle));
}
if (low[x] < ordre[x])
incycle.push_back(id);
else if (id >= 0)
notcycle.push_back(id);
return low[x];
}
int find(int x, vector<int> &p)
{
return (p[x] == x) ? x : p[x] = find(p[x], p);
}
int dfs2(int x, int par, int id, vector<int> &p, vector<vector<pair<int, int>>> &AR, vector<int> &cities, vector<char> &ans, vector<pair<int, int>> &aretes)
{
int cur = 0;
for (int i = 0; i < AR[x].size(); i++)
{
if (find(AR[x][i].first, p) == par)
continue;
if (find(AR[x][i].first, p) == x)
continue;
cur += dfs2(find(AR[x][i].first, p), x, AR[x][i].second, p, AR, cities, ans, aretes);
}
cur += cities[x];
if (id < 0)
return cur;
if (cur == 0)
ans[id] = 'B';
else
{
if (find(aretes[id].first, p) == x)
{
if (cur > 0)
ans[id] = 'R';
else
ans[id] = 'L';
}
else
{
if (cur > 0)
ans[id] = 'L';
else
ans[id] = 'R';
}
}
return cur;
}
int main()
{
int N, M;
cin >> N >> M;
vector<vector<pair<int, int>>> AR(N);
vector<pair<int, int>> aretes;
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
a--, b--;
AR[a].push_back({b, i});
AR[b].push_back({a, i});
aretes.push_back({a, b});
}
int buff = 0;
vector<int> low(N, N), ordre(N);
vector<int> incycle, notcycle;
dfs(0, 0, -1, AR, buff, ordre, low, incycle, notcycle);
vector<char> ans(M);
vector<int> p(N), size(N, 1);
for (int i = 0; i < N; i++)
p[i] = i;
for (int i = 0; i < incycle.size(); i++)
{
ans[incycle[i]] = 'B';
int x = find(aretes[incycle[i]].first, p), y = find(aretes[incycle[i]].second, p);
if (x == y)
continue;
if (size[x] > size[y])
swap(x, y);
p[x] = y;
size[y] += size[x];
for (int j = 0; j < AR[x].size(); j++)
AR[y].push_back(AR[x][j]);
}
int P;
cin >> P;
vector<int> cities(N, 0);
for (int i = 0; i < P; i++)
{
int a, b;
cin >> a >> b;
a--, b--;
cities[find(a, p)]++;
cities[find(b, p)]--;
}
int cur = 0;
int temp = dfs2(find(0, p), find(0, p), -1, p, AR, cities, ans, aretes);
for (int i = 0; i < M; i++)
cout << ans[i];
}
Compilation message
oneway.cpp: In function 'int dfs(int, int, int, std::vector<std::vector<std::pair<int, int> > >&, int&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
oneway.cpp:5:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | if (low[x] != low.size())
oneway.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int i = 0; i < AR[x].size(); i++)
| ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int dfs2(int, int, int, std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<int>&, std::vector<char>&, std::vector<std::pair<int, int> >&)':
oneway.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < AR[x].size(); i++)
| ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < incycle.size(); i++)
| ~~^~~~~~~~~~~~~~~~
oneway.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int j = 0; j < AR[x].size(); j++)
| ~~^~~~~~~~~~~~~~
oneway.cpp:110:9: warning: unused variable 'cur' [-Wunused-variable]
110 | int cur = 0;
| ^~~
oneway.cpp:111:9: warning: unused variable 'temp' [-Wunused-variable]
111 | int temp = dfs2(find(0, p), find(0, p), -1, p, AR, cities, ans, aretes);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
