QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#109419 | #6526. Canvas | wtz2333 | WA | 3ms | 26888kb | C++17 | 4.7kb | 2023-05-28 22:57:30 | 2023-05-28 22:57:35 |
Judging History
answer
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
const int maxn = 1000005;
int T;
struct OP {
int l, x, r, y;
};
typedef long long int ll;
std::vector<std::pair<int, int>> e1[maxn];
bool ctrl[maxn];
int dfn[maxn], low[maxn], stk[maxn], ins[maxn], top, vistime, scnt, sz[maxn], bel[maxn], ind[maxn], c[maxn], inv[maxn], frstv[maxn], inid[maxn];
void dfs(const int u) {
low[u] = dfn[u] = ++vistime;
ins[stk[++top] = u] = true;
for (auto [v,id] : e1[u]) if (!ctrl[v] && dfn[v] == 0) {
dfs(v);
low[u] = std::min(low[u], low[v]);
} else if (!ctrl[v] && ins[v]) {
low[u] = std::min(low[u], low[v]);
}
if (low[u] == dfn[u]) {
++scnt; int v;
do {
ins[v = stk[top--]] = false;
++sz[bel[v] = scnt];
frstv[scnt] = v;
} while (u != v);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
for (std::cin >> T; T; --T) {
int n, m;
std::cin >> n >> m;
std::vector<OP> op(m);
std::vector<int> ans1, ans2, ans3, ans4;
std::vector<int> prt(m + 1), vis(n + 1);
for (int i = 1; i <= std::max(n, m); ++i) {
e1[i].clear();
ctrl[i] = false;
dfn[i] = low[i] = stk[i] = ins[i] = bel[i] = sz[i] = ind[i] = c[i] = inv[i] = frstv[i] = inid[i] = 0;
}
top = vistime = scnt = 0;
// e1 : 1->2, e2 : 2->1
for (int i = 0; i < m; ++i) {
OP &u = op[i];
std::cin >> u.l >> u.x >> u.r >> u.y;
if (u.x > u.y) {
std::swap(u.x, u.y);
std::swap(u.l, u.r);
}
}
std::queue<int> Q;
for (int u = 0; u < m; ++u) {
OP i = op[u];
int l = i.l, r = i.r;
if (i.y == 2) {
if (i.x == 1) {
e1[l].push_back({r, u +1});
// e2[r].push_back(l);
} else {
if (!ctrl[l]) {
ctrl[l] = 1;
Q.push(l);
}
if (!ctrl[r]) {
ctrl[r] = 1;
Q.push(r);
}
ans3.push_back(1 + u);
}
}
}
for (int u; !Q.empty(); Q.pop()) {
u = Q.front();
for (auto [v, id] : e1[u]) if (!ctrl[v]) {
ans1.push_back(id);
ctrl[v] = 1;
Q.push(v);
}
}
std::reverse(ans1.begin(), ans1.end());
for (int i = 1; i <= n; ++i) if (!ctrl[i] && dfn[i] == 0) {
dfs(i);
}
int ans = 0;
for (int i = 1; i <= n; ++i) if (!ctrl[i]) {
for (auto [v,id] : e1[i]) if (!ctrl[v] && bel[i] != bel[v]) {
++ind[bel[v]]; inv[bel[v]] = v; inid[bel[v]] = id;
}
}
for (int i = 1; i <= n; ++i) if (!ctrl[i]) {
for (auto [v, id] : e1[i]) if (!ctrl[v]) {
if (c[i] < 1) {
++ans;
c[i] = 1;
}
if (c[v] < 2) {
ans += 2 - c[v];
c[v] = 2;
}
}
}
for (int i = 1; i <= scnt; ++i) if (!ind[i] && sz[i] > 1) {
--ans;
}
for (int i = 1; i <= n; ++i) if (ctrl[i]) {
c[i] = 2;
ans += 2;
}
for (auto i : op) if ((i.y == 1) || (i.x == 1 && ctrl[i.r])) {
if (c[i.l] == 0) {
c[i.l] = 1;
++ans;
}
if (c[i.r] == 0) {
c[i.r] = 1;
++ans;
}
}
std::cout << ans << '\n';
/* for (int i = 0; i < m; ++i) {
OP u = op[i];
if (u.y == 1) {
// ans1.push_back(i + 1);
// prt[i + 1] = true;
}
}*/
for (int i = 1; i <= scnt; ++i) if (inv[i]) {
std::vector<int> tmp;
vis[inv[i]] = 1;
for (Q.push(inv[i]); !Q.empty(); Q.pop()) {
for (auto [v, id] : e1[Q.front()]) if (bel[v] == i && vis[i] == 0) {
tmp.push_back(id);
Q.push(v);
vis[v] = 1;
}
}
std::reverse(tmp.begin(), tmp.end());
for (auto u : tmp) ans2.push_back(u);
ans2.push_back(inid[i]);
} else if (sz[i] != 1) {
std::vector<int> tmp;
vis[frstv[i]] = 1;
for (Q.push(frstv[i]); !Q.empty(); Q.pop()) {
for (auto [v, id] : e1[Q.front()]) if (bel[v] == i && vis[i] == 0) {
tmp.push_back(id);
Q.push(v);
vis[v] = 1;
}
}
std::reverse(tmp.begin(), tmp.end());
for (auto u : tmp) ans2.push_back(u);
}
for (auto i : ans2) prt[i] = true;
for (auto i : ans1) prt[i] = true;
for (auto i : ans3) prt[i] = true;
for (int i = 1; i <= m; ++i) if (prt[i] == false) {
std::cout << i << ' ';
}
for (auto i : ans2) std::cout << i << ' ';
for (auto i : ans1) std::cout << i << ' ';
for (auto i : ans3) std::cout << i << ' ';
std::cout << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 26888kb
input:
2 4 4 1 1 2 2 3 2 4 1 1 2 3 2 2 1 4 1 4 2 3 2 4 1 1 2 3 1
output:
7 2 4 1 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 26884kb
input:
1 10 13 1 1 2 2 2 1 3 2 1 2 3 1 3 1 4 2 4 1 5 2 5 1 6 2 4 2 6 1 7 1 8 2 8 1 9 2 7 2 9 1 5 2 9 1 8 2 10 2 1 1 10 1
output:
19 1 2 3 4 5 8 13 7 6 11 10 9 12
result:
wrong answer Participant's solution is incorrect. (test case 1)