QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#453934 | #6526. Canvas | NGDtuanh | WA | 12ms | 51784kb | C++17 | 3.8kb | 2024-06-24 15:00:50 | 2024-06-24 15:00:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define RFor(i, a, b) for (int i = a; i >= b; --i)
#define get_bit(bit, mask) (((mask) >> (bit)) & 1)
const int N = 5e5 + 5;
int INF = 2e18 + 5;
int MOD = 1e9 + 7;
int sum;
vector<int> ans;
int n, m;
int a[N];
int l[N], x[N], r[N], y[N];
int vis[N];
vector<pair<int, int>> adj[N];
int num[N], low[N], del[N], cur;
int sccId[N];
int sccVis[N];
vector<vector<int>> scc;
int savable[N];
vector<int> sccSavable;
vector<pair<int, int>> sccAdj[N];
stack<int> stk;
void GetInput() {
cin >> n >> m;
For(i, 1, m) cin >> l[i] >> x[i] >> r[i] >> y[i];
}
void Rep() {
cout << accumulate(a + 1, a + n + 1, 0ll) << '\n';
for (int e : ans) cout << e << ' ';
cout << '\n';
}
void Clear() {
ans.clear();
fill(a, a + m + 1, 0);
For(i, 0, n) adj[i].clear();
fill(vis, vis + n + 1, 0);
fill(num, num + n + 1, 0);
fill(low, low + n + 1, 0);
fill(del, del + n + 1, 0);
fill(sccVis, sccVis + n + 1, 0);
fill(sccId, sccId + n + 1, 0);
fill(savable, savable + n + 1, 0);
cur = 0;
scc.clear();
sccSavable.clear();
For(i, 0, n) sccAdj[i].clear();
}
void BuildSCC(int node) {
num[node] = low[node] = ++cur;
stk.push(node);
for (auto [child, id] : adj[node]) {
if (del[child]) continue;
if (num[child]) low[node] = min(low[node], num[child]);
else BuildSCC(child), low[node] = min(low[node], low[child]);
}
if (num[node] == low[node]) {
sccId[node] = scc.size();
scc.emplace_back();
sccSavable.emplace_back();
scc.back().push_back(node);
del[node] = true;
while (stk.top() != node)
sccId[stk.top()] = sccId[node],
scc.back().push_back(stk.top()),
del[stk.top()] = true,
stk.pop();
stk.pop();
}
}
void DFS(int node) {
vis[node] = true;
for (auto [child, id] : adj[node]) {
if (sccId[child] != sccId[node]) continue;
if (!vis[child]) DFS(child);
ans.push_back(id);
}
}
void Topo(int node) {
sccVis[node] = true;
int startPnt = scc[node].front();
if (sccSavable[node] != 0) startPnt = sccSavable[node];
for (auto [child, id] : sccAdj[node]) {
if (!sccVis[child]) Topo(child);
ans.push_back(id);
}
DFS(startPnt);
}
void Solve() {
Clear();
For(i, 1, m)
if (x[i] == 1 && y[i] == 1)
ans.push_back(i);
For(i, 1, m)
if (x[i] == 1 && y[i] == 2)
adj[l[i]].push_back({ r[i], i });
else if (x[i] == 2 && y[i] == 1)
adj[r[i]].push_back({ l[i], i });
For(i, 1, n)
if (num[i] == 0)
BuildSCC(i);
For(i, 1, m)
if (x[i] == 2 && y[i] == 2)
savable[l[i]] = true,
savable[r[i]] = true;
For(i, 0, (int)scc.size() - 1)
for (int node : scc[i]) {
if (savable[node] == true) sccSavable[i] = node;
for (auto [child, id] : adj[node])
if (sccId[node] != sccId[child])
sccSavable[sccId[child]] = child,
sccAdj[sccId[node]].push_back({ sccId[child], id });
}
For(i, 0, (int)scc.size() - 1)
if (!sccVis[i])
Topo(i);
For(i, 1, m)
if (x[i] == 2 && y[i] == 2)
ans.push_back(i);
for (int i : ans)
a[l[i]] = x[i],
a[r[i]] = y[i];
}
signed main() {
#ifndef LOCAL
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
int t; cin >> t;
while (t--) {
GetInput();
Solve();
Rep();
}
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 51164kb
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: 0ms
memory: 48324kb
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 5 7 6 4 3 2 1 11 8 10 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 48848kb
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: 50388kb
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: 12ms
memory: 51052kb
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 3 4 1 5 2
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 51784kb
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: 8ms
memory: 50168kb
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 10 1 9 13 3 11 15 14 2 8 5 6 4 16 12 20 14 1 13 10 9 8 12 11 3 15 6 2 5 7 4 21 2 6 10 3 11 13 9 12 7 8 4 1 14 5 20 7 4 8 12 13 6 10 14 11 1 5 3 9 2 21 6 17 8 4 5 3 2 7 11 14 10 13 16 19 1 18 12 9 15 21 3 9 14 5 13 8 4 10 11 7 12 2 6 1 21 3 8 1 5 15 6 7 11 9 13 4 12 2 14 10 19 11 7 10 16 ...
result:
wrong answer Participant's solution is incorrect. (test case 4)