QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#453924 | #6526. Canvas | NGDtuanh | WA | 3ms | 51464kb | C++17 | 4.1kb | 2024-06-24 14:55:17 | 2024-06-24 14:55:17 |
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 + m + 1, 0ll) << '\n';
for (int e : ans) cout << e << ' ';
cout << '\n';
}
void Clear() {
ans.clear();
fill(a, a + m + 1, 0);
For(i, 1, 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, 1, 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) {
// cout << node << '\n';
vis[node] = true;
for (auto [child, id] : adj[node]) {
if (sccId[child] != sccId[node]) continue;
if (!vis[child]) DFS(child);
ans.push_back(id);
// cout << "push: " << id << '\n';
}
}
void Topo(int node) {
// cout << node << '\n';
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);
// cout << "push: " << id << '\n';
}
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);
// cout << scc.size() << '\n';
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 });
}
// cout << "\n\n";
// For(i, 0, (int)scc.size() - 1) cout << sccVis[i] << ' ';
// cout << '\n';
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: 0
Wrong Answer
time: 3ms
memory: 51464kb
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 2 2 1
result:
wrong answer Participant's solution is incorrect. (test case 2)