QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#446608 | #4809. Maximum Range | IBory | WA | 104ms | 36816kb | C++20 | 3.3kb | 2024-06-17 13:59:06 | 2024-06-17 13:59:06 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAX = 100007;
vector<pii> G[MAX], BCC[MAX];
int V[MAX], E[MAX], B[MAX], pv[MAX], ok[MAX], dn, bn;
set<pii> no;
vector<int> S;
pii P[MAX];
int DFS(int cur, int prev) {
int ret = V[cur] = ++dn;
for (auto [next, en] : G[cur]) {
if (next == prev) continue;
if (V[cur] > V[next]) S.push_back(en);
if (V[next]) {
ret = min(ret, V[next]);
continue;
}
int t = DFS(next, cur);
ret = min(ret, t);
if (t < V[cur]) continue;
bn++;
do {
int e = S.back(); S.pop_back();
B[e] = bn;
BCC[bn].emplace_back(E[e], e);
} while (BCC[bn].back().second != en);
sort(BCC[bn].begin(), BCC[bn].end());
}
return ret;
}
const int MAX_N = 222222;
const int MAX_E = 666666;
struct Dinic {
vector<pii> G[MAX_N];
int lim[MAX_E], use[MAX_E], en = 2;
int lv[MAX_N], idx[MAX_N], src, snk;
set<int> in;
void AddEdge(int a, int b, int c) {
G[a].emplace_back(b, en);
G[b].emplace_back(a, en ^ 1);
lim[en] = c;
en += 2;
}
bool BFS() {
memset(lv, -1, sizeof(lv));
queue<int> Q;
Q.push(src);
lv[src] = 0;
while (!Q.empty()) {
int cur = Q.front(); Q.pop();
for (auto [next, en] : G[cur]) {
if (lv[next] != -1 || lim[en] == use[en]) continue;
lv[next] = lv[cur] + 1;
Q.push(next);
}
}
return lv[snk] != -1;
}
int DFS(int cur, int res = 1e9) {
if (cur == snk) return res;
for (int& i = idx[cur]; i < G[cur].size(); ++i) {
auto& [next, en] = G[cur][i];
if (lv[cur] + 1 != lv[next] || lim[en] == use[en]) continue;
int f = DFS(next, min(res, lim[en] - use[en]));
if (f) {
if (in.count(en ^ 1)) in.erase(en ^ 1);
in.insert(en);
use[en] += f;
use[en ^ 1] -= f;
return f;
}
}
return 0;
}
int Flow(int S, int E) {
src = S, snk = E;
int ret = 0;
while (BFS() && ret < 2) {
memset(idx, 0, sizeof(idx));
int t = 0;
while (t = DFS(src)) ret += t;
}
return ret;
}
} F;
vector<int> ans;
void DFS2(int cur, int prev) {
for (auto [next, en] : G[cur]) {
if (!ok[en] || next == prev || next == ans[0]) continue;
ans.push_back(next);
DFS2(next, cur);
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
int a, b;
cin >> a >> b >> E[i];
G[a].emplace_back(b, i);
G[b].emplace_back(a, i);
P[i] = {a, b};
}
DFS(1, 0);
int go = -1, id = 0;
for (int i = 1; i <= bn; ++i) {
if (BCC[i].size() == 1) continue;
int n = BCC[i].back().first - BCC[i][0].first;
if (go < n) {
go = n;
id = i;
}
}
auto [a, b] = P[BCC[id][0].second];
auto [c, d] = P[BCC[id].back().second];
ok[BCC[id][0].second] = ok[BCC[id].back().second] = 1;
int src = 2 * N + 1, snk = 2 * N + 2;
for (int i = 1; i <= M; ++i) {
auto [u, v] = P[i];
F.AddEdge(N + u, v, 1);
F.AddEdge(N + v, u, 1);
}
for (int i = 1; i <= N; ++i) F.AddEdge(i, N + i, 1);
F.AddEdge(src, a, 1); F.AddEdge(src, b, 1);
F.AddEdge(N + c, snk, 1); F.AddEdge(N + d, snk, 1);
F.Flow(src, snk);
for (int n : F.in) {
int e = n / 4;
if (e <= M) ok[e] = 1;
}
ans.push_back(a);
DFS2(a, a);
cout << go << '\n';
cout << ans.size() << '\n';
for (int n : ans) cout << n << ' ';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12808kb
input:
5 7 1 2 1 1 3 -2 2 3 1 3 4 3 4 5 1 1 5 -1 2 5 2
output:
5 5 1 3 4 5 2
result:
ok ok
Test #2:
score: -100
Wrong Answer
time: 104ms
memory: 36816kb
input:
99997 100000 12238 99016 352755196 99016 25485 -412473602 25485 2440 991507552 2440 31171 -181894654 36970 2440 -800167579 2440 41865 -148191946 96629 31171 847888506 36970 95740 395546542 27992 2440 647886610 99016 29557 369124914 80795 27992 -673871966 36970 3509 573208857 57672 29557 874406776 41...
output:
1959330954 7 95092 31171 2440 25485 99016 27992 43946
result:
wrong answer Edge 99016-27992 does not appear in original graph