QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#260286 | #1195. One-Way Conveyors | lemonilemon# | WA | 47ms | 8496kb | C++20 | 4.6kb | 2023-11-21 23:48:12 | 2023-11-21 23:48:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef genshin
#include <experimental/iterator>
#endif
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using uint = unsigned int;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 46 * ll(1e17);
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 25;
namespace bridge_cc {
vector<int> tim, low;
stack<int, vector<int>> st;
int t, bcc_id;
void dfs(int u, int p, const vector<vector<pair<int, int>>> &edge, vector<int> &pa) {
tim[u] = low[u] = t++;
st.push(u);
for (const auto &[v, id] : edge[u]) {
if (id == p)
continue;
if (tim[v])
low[u] = min(low[u], tim[v]);
else {
dfs(v, id, edge, pa);
if (low[v] > tim[u]) {
int x;
do {
pa[x = st.top()] = bcc_id;
st.pop();
} while (x != v);
bcc_id++;
}
else
low[u] = min(low[u], low[v]);
}
}
}
vector<int> solve(const vector<vector<pair<int, int>>> &edge) {
int n = edge.size();
tim.resize(n);
low.resize(n);
t = bcc_id = 1;
vector<int> pa(n);
for (int i = 0; i < n; i++) {
if (!tim[i]) {
dfs(i, -1, edge, pa);
while (!st.empty()) {
pa[st.top()] = bcc_id;
st.pop();
}
bcc_id++;
}
}
return pa;
}
};
signed main() { ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
vector<vector<pair<int, int>>> edge(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--; v--;
edge[u].push_back({v, i});
edge[v].push_back({u, i});
edges[i] = {u, v};
}
auto pa = bridge_cc::solve(edge);
int t = *max_element(pa.begin(), pa.end());
vector<vector<pair<int, int>>> nw_edge(t + 1);
vector<vector<pair<int, int>>> eve(t + 1);
map<pair<int, int>, pair<int, int>> ori;
for (int i = 0; i < m; i++) {
auto [u, v] = edges[i];
auto [a, b] = edges[i];
u = pa[u];
v = pa[v];
if (u == v)
continue;
nw_edge[u].push_back({v, i});
nw_edge[v].push_back({u, i + m});
ori[{u, v}] = {a, b};
ori[{v, u}] = {b, a};
}
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
a = pa[a];
b = pa[b];
eve[a].push_back({i, 1});
eve[b].push_back({i, -1});
}
vector<bool> vis(t + 1);
bool ok = true;
vector<pair<int, int>> ans;
function<map<int, int>(int)> dfs = [&] (int u) {
vis[u] = true;
map<int, int> has;
for (const auto &[tar, dir] : eve[u]) {
if (has.count(tar))
has.erase(tar);
else
has[tar] = dir;
}
for (const auto &[v, i] : nw_edge[u]) {
if (vis[v])
continue;
auto owo = dfs(v);
if (has.size() < owo.size())
swap(has, owo);
int cur = 0;
for (const auto &[tar, dir]: owo) {
if (!cur)
cur = dir;
else {
if (cur != dir)
ok = false;
}
if (has.count(tar))
has.erase(tar);
else
has[tar] = dir;
}
auto [a, b] = ori[{u, v}];
if (cur == 1)
swap(a, b);
ans.push_back({a, b});
}
return has;
};
for (int i = 1; i <= t; i++)
if (!vis[i])
dfs(i);
if (!ok) {
cout << "No\n";
return 0;
}
vector<int> tim(n);
int num = 1;
function<void(int)> solve = [&] (int u) {
tim[u] = num++;
for (const auto &[v, i] : edge[u]) {
if (pa[v] != pa[u])
continue;
if (tim[v] && tim[v] < tim[u])
continue;
if (tim[v]) {
ans.push_back({v, u});
}
else {
solve(v);
ans.push_back({u, v});
}
}
};
for (int i = 0; i < n; i++)
if (!tim[i])
solve(i);
cout << "Yes\n";
for (const auto &[a, b] : ans)
cout << a + 1 << ' ' << b + 1 << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3832kb
input:
3 2 1 2 2 3 3 1 2 1 3 2 3
output:
Yes 1 2 2 3
result:
ok OK!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 2 1 2 2 3 3 1 2 1 3 3 2
output:
No
result:
ok OK!
Test #3:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
4 4 1 2 1 3 1 4 2 3 7 1 2 1 3 1 4 2 1 2 3 3 1 3 2
output:
Yes 1 4 2 3 1 2 3 1
result:
ok OK!
Test #4:
score: 0
Accepted
time: 26ms
memory: 6908kb
input:
9990 47670 134 2450 4227 9100 1861 9948 120 8957 1161 4767 76 1714 5207 5838 2726 8974 2489 8619 2379 4933 3675 9554 344 3215 1654 6168 5630 6614 3247 5202 4456 5373 4380 6605 2626 4064 2194 6332 2749 9719 360 5059 7967 8835 5433 6494 497 6638 5945 9063 7576 7879 3550 4107 83 2891 3107 6917 2089 689...
output:
No
result:
ok OK!
Test #5:
score: 0
Accepted
time: 47ms
memory: 8496kb
input:
3219 13421 762 2133 1106 2880 2287 2476 313 992 741 1903 811 2050 1468 2184 3031 3037 403 1855 1060 1415 1792 2804 772 2956 140 2281 808 1953 895 1731 1217 1551 1264 1885 749 1082 1564 2824 1549 1741 1966 2730 112 2825 158 2625 2128 2917 128 3032 644 3194 1634 2743 1545 1961 2402 2680 2663 2814 1040...
output:
No
result:
ok OK!
Test #6:
score: 0
Accepted
time: 21ms
memory: 5484kb
input:
8013 18891 6127 6374 3969 4617 215 2699 268 6282 167 5415 1318 6256 3994 6192 4325 7186 1785 4188 6570 7153 772 5901 9 5190 873 6509 161 7476 2960 2966 4598 7170 1157 3798 758 4508 1446 5205 445 5989 686 5479 669 4711 6254 6860 1722 7020 463 3494 5063 7309 2231 6762 1208 4304 4789 5081 3925 6248 107...
output:
No
result:
ok OK!
Test #7:
score: -100
Wrong Answer
time: 11ms
memory: 5988kb
input:
9968 46595 3655 5544 5747 9340 6020 9528 5789 9882 4609 8832 1969 5167 2610 8012 324 9387 694 3647 3667 8483 4202 4963 2643 8104 1139 9679 1407 7022 9031 9944 5183 8744 3341 3858 326 2610 414 1317 657 7942 4702 5671 2072 3200 3074 3597 26 3728 288 7757 144 9580 1374 2065 2683 8068 1341 6526 2140 257...
output:
No
result:
wrong answer Output doesn't match the expected answer