QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110195 | #6526. Canvas | Fu_su | ML | 6ms | 22196kb | C++17 | 5.2kb | 2023-06-01 03:05:27 | 2023-06-01 03:05:30 |
Judging History
answer
#include "assert.h"
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
const int maxn = 500005;
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;
assert(std::max(n, m) <= 100);
std::vector<OP> op(m);
std::vector<int> ans1, ans2, ans3, ans4;
std::vector<int> prt(m + 1), vis(n + 1);
for (int i = 0; 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::cerr << i << '\n';
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::cerr << frstv[i] << '\n';
// std::cerr << ans2.size() << '\n';
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[v] == 0) {
// std::cerr << Q.front() << ' ' << v << ' ' << id << '\n';
tmp.push_back(id);
Q.push(v);
vis[v] = 1;
} else {
// std::cerr << Q.front() << ' ' << v << '\n';
}
}
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 << ' ';
}
// return 0;
for (auto i : ans2) std::cout << i << ' ';
for (auto i : ans1) std::cout << i << ' ';
for (auto i : ans3) std::cout << i << ' ';
std::cout << '\n';
}
}
/**********************************************************************
Problem: 1011
User: team010
Language: C++
Result: RE
**********************************************************************/
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 22096kb
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: 0
Accepted
time: 2ms
memory: 19340kb
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 3 4 5 8 13 2 1 7 6 11 10 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 2ms
memory: 17968kb
input:
1 7 5 2 1 6 2 1 2 6 1 1 1 5 1 2 2 7 1 1 1 7 2
output:
8 2 3 1 4 5
result:
ok Correct. (1 test case)
Test #4:
score: 0
Accepted
time: 4ms
memory: 22196kb
input:
1 7 6 2 1 7 2 2 1 4 2 1 2 4 1 2 1 6 1 1 1 6 2 2 2 6 1
output:
9 3 4 1 2 6 5
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 1ms
memory: 21992kb
input:
1 7 5 5 2 7 1 5 1 6 2 3 2 7 1 3 2 6 1 6 1 7 2
output:
7 1 4 3 5 2
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 1ms
memory: 20348kb
input:
1 7 6 1 2 5 1 2 1 7 2 1 2 7 1 2 2 7 1 1 1 5 2 1 2 3 1
output:
8 1 4 5 6 3 2
result:
ok Correct. (1 test case)
Test #7:
score: -100
Memory Limit Exceeded
input:
2000 15 16 2 2 3 1 12 2 15 1 3 2 9 1 6 2 14 1 2 1 15 2 5 2 6 1 7 1 10 1 9 2 15 1 2 2 3 1 4 2 12 1 2 2 9 1 5 2 8 2 3 2 13 1 12 1 13 2 9 2 13 1 5 1 14 2 15 15 5 2 11 1 1 2 8 1 8 1 15 2 6 2 8 2 8 2 9 1 1 1 6 2 6 1 9 2 2 2 5 1 2 1 10 2 7 2 10 1 1 1 15 2 5 2 15 1 7 1 11 2 1 1 2 1 5 2 9 1 15 14 3 1 5 2 1 ...