QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#371186 | #6526. Canvas | Nelofus | WA | 8ms | 36856kb | C++20 | 3.4kb | 2024-03-30 01:31:54 | 2024-03-30 01:31:55 |
Judging History
answer
/*
* Copyright© 2024 Heratino & Nelofus. All rights reserved.
* author: Heratino & Nelofus
* Problem:
* Tag:
* Memory Limit:
* Time Limit:
* Source:
*/
// Narcissus & どうか安寧な記憶を
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 5e5 + 10;
struct operators {
int l, r, x, y;
int type;
int id;
} qry[N];
int n, m;
int dfn[N], low[N], dfc, sn;
int number[N];
bool instk[N];
int stk[N], tt;
std::basic_string<int> scc[N];
std::vector<operators> edg[N];
std::basic_string<int> G[N];
void dfs(int u) {
dfn[u] = low[u] = ++dfc;
stk[++tt] = u;
instk[u] = true;
for (const int &v : G[u]) {
if (!dfn[v]) {
dfs(v);
low[u] = std::min(low[u], low[v]);
} else if (instk[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
sn++;
while (stk[tt] != u) {
instk[stk[tt]] = false;
number[stk[tt]] = sn;
scc[sn].push_back(stk[tt--]);
}
instk[stk[tt]] = false;
number[stk[tt]] = sn;
scc[sn].push_back(stk[tt--]);
}
}
void tarjan() {
for (int i = 1; i <= n; i++)
if (!dfn[i])
dfs(i);
}
int ans[N];
int ind[N];
int tp[N];
int dis[N];
void clear(int n, int m) {
for (int i = 1; i <= n; i++) G[i].clear();
for (int i = 1; i <= sn; i++) scc[i].clear();
memset(dfn + 1, 0, n * sizeof(int));
memset(low + 1, 0, n * sizeof(int));
memset(ans + 1, 0, n * sizeof(int));
memset(ind + 1, 0, n * sizeof(int));
dfc = 0, sn = 0;
memset(dis + 1, 0x3f, n * sizeof(int));
}
inline void add(int u, int v) {G[u] += v;}
void bfs() {
std::queue<int> q;
dfc = 0;
for (int i = 1; i <= sn; i++)
if (ind[i] == 0)
q.push(scc[i][0]), dis[scc[i][0]] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (const int &v : G[u]) {
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
}
void solve() {
std::cin >> n >> m;
clear(n, m);
for (int i = 1; i <= m; i++) {
auto &[l, r, x, y, type, id] = qry[i];
std::cin >> l >> x >> r >> y;
if (x == 1 && y == 1)
type = 0;
else if (x == 2 && y == 2)
type = 2;
else
type = 1;
id = i;
}
std::sort(qry + 1, qry + 1 + m, [&](operators a, operators b) {
return a.type < b.type;
});
for (int i = 1; i <= m; i++) {
auto &[l, r, x, y, type, id] = qry[i];
if (x == 1 && y == 2)
add(r, l);
if (x == 2 && y == 1)
add(l, r);
}
tarjan();
for (int u = 1; u <= n; u++)
for (const int &v : G[u]) {
if (number[u] != number[v]) {
ind[number[v]]++;
}
}
bfs();
std::sort(qry + 1, qry + 1 + m, [&](operators a, operators b) {
if (a.type == 1 && b.type == 1) {
int t1 = (a.x == 1 ? a.l : a.r);
int t2 = (b.x == 1 ? b.l : b.r);
return dis[t1] < dis[t2];
}
return a.type < b.type;
});
for (int i = m; i >= 1; i--) {
auto &[l, r, x, y, type, id] = qry[i];
if (ans[l] == 0)
ans[l] = x;
if (ans[r] == 0)
ans[r] = y;
}
int res = 0;
for (int i = 1; i <= n; i++)
res += ans[i];
std::cout << res << '\n';
// 正序输出
for (int i = 1; i <= m; i++)
std::cout << qry[i].id << " \n"[i == m];
}
/* 无法忘却的记忆与苍蓝之梦 */
int main() {
#ifdef HeratinoNelofus
freopen("input.txt", "r", stdin);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
std::cin >> T;
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 36140kb
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: -100
Wrong Answer
time: 8ms
memory: 36856kb
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:
17 13 6 5 10 11 3 4 7 9 2 8 1 12
result:
wrong answer Jury has better answer. Participant 17, jury 19 (test case 1)