QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110197 | #6526. Canvas | Fu_su | RE | 15ms | 3536kb | C++17 | 5.5kb | 2023-06-01 03:11:30 | 2023-06-01 03:11:33 |
Judging History
answer
#include "assert.h"
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
const int maxn = 100;
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 clear() {
for (auto &x : e1) x.clear();
#define clr(x) memset(x, 0, sizeof(x))
clr(ctrl);
clr(dfn);
clr(low);
clr(stk);
clr(ins);
clr(sz);
clr(bel);
clr(ind);
clr(c);
clr(inv);
clr(frstv);
clr(inid);
top = vistime = scnt = 0;
}
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);
clear();
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[v] == 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: 2ms
memory: 3436kb
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: 0ms
memory: 3432kb
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: 1ms
memory: 3476kb
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: 2ms
memory: 3492kb
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: 2ms
memory: 3436kb
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: 2ms
memory: 3536kb
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 6 5 3 2
result:
ok Correct. (1 test case)
Test #7:
score: 0
Accepted
time: 8ms
memory: 3496kb
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 ...
output:
23 1 6 7 9 11 13 15 10 3 14 8 2 5 4 16 12 20 1 5 6 11 12 14 13 10 9 8 15 3 2 7 4 21 2 6 8 11 14 10 13 3 9 12 4 7 1 5 18 3 4 7 9 11 13 14 1 5 8 12 6 10 2 21 1 2 3 5 6 7 11 12 16 18 14 10 13 19 9 17 8 4 15 21 2 3 9 11 13 6 14 8 5 7 4 12 10 1 21 2 3 7 8 11 15 1 5 14 9 6 13 4 12 10 19 2 3 7 9 11 ...
result:
ok Correct. (2000 test cases)
Test #8:
score: 0
Accepted
time: 15ms
memory: 3476kb
input:
2000 15 18 10 1 15 2 10 1 15 2 3 2 13 1 5 1 6 2 2 1 10 2 3 2 5 2 7 1 12 2 2 2 3 1 12 1 13 2 5 2 11 1 7 1 15 2 5 1 15 2 6 1 11 2 2 1 6 1 5 1 10 2 5 2 10 1 2 1 7 2 2 1 15 2 15 17 7 2 15 1 6 2 10 1 3 2 12 1 13 2 14 1 1 1 7 2 6 2 15 1 6 2 13 2 1 2 6 1 10 2 15 1 12 2 15 1 9 1 10 2 13 1 15 2 9 2 12 1 3 1 ...
output:
20 1 2 3 5 10 11 14 16 18 9 7 13 17 15 12 4 8 6 21 1 2 4 6 11 13 16 17 14 3 10 9 15 5 12 8 7 21 1 2 6 8 9 10 11 13 15 16 3 5 4 17 12 18 7 14 19 1 4 5 8 9 11 12 13 14 18 3 2 15 6 10 16 7 17 19 1 3 4 9 11 14 15 16 7 12 10 8 5 13 2 6 21 3 4 9 10 11 6 12 1 7 8 13 5 2 20 2 6 8 9 13 4 1 11 7 10 12 3...
result:
ok Correct. (2000 test cases)
Test #9:
score: 0
Accepted
time: 2ms
memory: 3500kb
input:
5 27 33 18 2 23 1 13 1 23 2 2 1 7 2 4 2 7 1 2 1 4 2 9 1 27 2 26 2 27 1 3 2 11 1 2 1 4 2 12 1 18 2 4 2 7 1 25 2 26 1 12 1 17 2 5 1 27 2 5 2 22 1 13 2 25 1 2 1 4 2 4 2 7 1 2 2 26 1 4 2 7 1 2 2 7 1 2 2 17 1 19 1 26 1 3 2 24 1 11 1 24 2 3 2 24 1 3 1 9 2 18 1 22 2 9 1 11 2 5 2 23 2 12 2 17 1 2 2 7 1 4 2 ...
output:
33 2 4 5 6 8 9 10 11 15 17 18 20 21 22 23 24 26 31 32 25 29 27 13 3 16 19 12 28 7 33 1 14 30 37 3 5 7 8 9 10 14 19 20 21 22 25 6 4 17 13 2 16 24 27 26 28 1 11 18 15 23 12 38 2 3 5 7 12 15 16 20 21 22 24 25 26 27 28 30 31 32 33 34 23 6 14 11 29 35 10 4 9 13 19 18 8 1 36 17 34 2 4 5 7 9 10 12 13 14...
result:
ok Correct. (5 test cases)
Test #10:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
5 27 37 10 2 25 2 18 2 22 1 18 1 22 2 2 1 24 2 14 2 26 1 4 1 27 2 15 2 25 1 24 1 27 2 7 2 20 1 11 1 18 1 2 1 14 2 15 1 25 2 10 2 15 1 9 1 16 2 24 2 27 1 24 1 27 2 10 2 12 1 10 1 15 2 9 2 14 1 6 1 15 2 7 1 27 2 24 1 27 2 6 1 22 2 16 1 20 2 15 1 24 2 4 1 27 2 24 1 27 2 2 1 4 2 24 2 27 1 7 1 26 2 24 1 ...
output:
35 3 4 5 6 7 8 10 12 13 15 16 17 20 21 22 23 26 27 29 31 32 35 36 2 33 30 9 24 14 19 11 28 37 34 25 18 1 37 6 7 8 10 11 16 17 20 22 23 26 27 28 29 30 31 32 19 18 3 21 4 25 34 14 33 15 13 12 9 2 24 5 1 35 1 2 11 12 13 14 17 18 19 21 22 23 25 26 27 29 33 34 10 5 15 32 7 16 31 20 6 24 4 8 9 30 3 28 ...
result:
ok Correct. (5 test cases)
Test #11:
score: -100
Dangerous Syscalls
input:
200 739 1933 110 1 669 2 17 2 403 1 39 1 538 2 36 2 267 1 66 2 259 1 55 2 483 1 245 2 450 1 30 1 729 2 318 1 568 2 344 1 681 2 11 2 37 1 15 2 192 1 55 2 344 1 426 2 596 1 3 2 683 1 499 1 614 1 302 1 367 2 220 1 528 1 223 2 563 1 255 2 719 1 153 2 688 1 371 2 648 1 704 2 715 1 367 2 477 1 451 2 698 2...