QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234313 | #6526. Canvas | ucup-team1198# | WA | 38ms | 34840kb | C++20 | 2.7kb | 2023-11-01 15:49:48 | 2023-11-01 15:49:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
const int MAXN = 5e5 + 100;
vector<array<int, 2>> g[MAXN];
vector<int> e[MAXN];
int used[MAXN], res[MAXN];
vector<int> ans;
void dfs(int v) {
used[v] = true;
for (auto e : g[v]) {
int u = e[0], id = e[1];
if (!used[u]) {
dfs(u);
}
res[u] = 2;
res[v] = 1;
ans.push_back(id);
}
}
vector<int> top;
void build_top(int v) {
used[v] = true;
for (int u : e[v]) {
if (!used[u]) {
build_top(u);
}
}
top.push_back(v);
}
int col[MAXN];
int is_start[MAXN];
void color(int v, int c) {
col[v] = c;
for (auto e : g[v]) {
int u = e[0];
if (col[u] == 0) {
color(u, c);
} else if (col[u] != c) {
is_start[col[u]] = 0;
}
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
g[i].clear();
}
ans.clear();
fill(used, used + n, 0);
fill(res, res + n, 0);
vector<int> good;
vector<int> start, fin;
for (int i = 0; i < m; ++i) {
int u, v, x, y;
cin >> u >> x >> v >> y;
x--; y--;
u--; v--;
if (x + y == 0) {
start.push_back(i);
res[u] = res[v] = 1;
continue;
}
if (x + y == 2) {
fin.push_back(i);
good.push_back(u);
good.push_back(v);
continue;
}
if (x == 1) {
swap(u, v);
}
g[u].push_back({v, i});
e[v].push_back(u);
}
top.clear();
for (int i = 0; i < n; ++i) {
if (!used[i]) {
build_top(i);
}
}
reverse(top.begin(), top.end());
int c = 1;
fill(col, col + n, 0);
for (int i : top) {
if (col[i] == 0) {
is_start[c] = 1;
color(i, c++);
}
}
fill(used, used + n, 0);
for (int v : good) {
if (!used[v]) {
dfs(v);
}
}
for (int i = 0; i < n; ++i) {
if (!used[i] && is_start[col[i]]) {
dfs(i);
}
}
for (int v : good) {
res[v] = 2;
}
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += res[i];
}
cout << sum << "\n";
for (int i : start) {
cout << i + 1 << " ";
}
for (int i : ans) {
cout << i + 1 << " ";
}
for (int i : fin) {
cout << i + 1 << " ";
}
cout << "\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tst;
cin >> tst;
while (tst--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 34596kb
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 4 1 2 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: 0
Accepted
time: 4ms
memory: 34452kb
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 13 8 10 5 7 6 11 9 3 4 2 1 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 34152kb
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 3 2 1 4 5
result:
ok Correct. (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 33860kb
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 4 1 3 2 6 5
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 0ms
memory: 34384kb
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 4 1 3 5 2
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 34840kb
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 5 3 4 2 6
result:
ok Correct. (1 test case)
Test #7:
score: -100
Wrong Answer
time: 38ms
memory: 34040kb
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 7 6 4 16 10 1 9 13 3 11 15 14 2 8 5 12 20 14 6 1 13 10 9 8 12 11 2 3 5 15 7 4 21 2 14 8 4 1 6 10 3 11 13 9 12 7 5 18 7 4 8 12 13 6 10 14 11 1 5 3 9 2 21 6 5 17 8 4 1 12 18 9 3 2 7 10 13 11 14 16 19 15 21 3 9 14 5 13 8 4 10 11 7 12 2 6 1 21 3 15 6 7 11 9 13 4 12 8 1 5 2 14 10 19 11 7 10 15 ...
result:
wrong answer Integer parameter [name=p_i] equals to 19, violates the range [1, 18] (test case 40)