QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473092 | #8136. Rebellious Edge | ucup-team1198# | WA | 66ms | 3876kb | C++20 | 1.9kb | 2024-07-11 21:47:21 | 2024-07-11 21:47:25 |
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 inf = 1e9 + 7;
void dfs(int u, vector<int>& used, vector<vector<int>>& g) {
used[u] = 1;
for (int i : g[u]) {
if (!used[i]) {
dfs(i, used, g);
}
}
}
void solve() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
vector<vector<pair<int, int>>> ag(n);
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a, --b;
g[a].push_back({b, c});
ag[b].push_back({a, c});
}
vector<pair<int, int>> be(n);
vector<vector<int>> gg(n);
ll sum = 0;
int bad_one = -1;
for (int i = 1; i < n; ++i) {
pair<int, int> bei = {-1, inf};
for (auto p : ag[i]) {
if (p.second < bei.second) {
bei = p;
}
}
be[i] = bei;
gg[be[i].first].push_back(i);
sum += be[i].second;
if (be[i].first > i) {
bad_one = i;
}
}
vector<int> used(n);
dfs(0, used, gg);
bool ok = 1;
for (int i = 0; i < n; ++i) {
if (used[i] == 0) ok = 0;
}
if (ok) {
cout << sum << '\n';
return;
}
vector<int> in_c(n);
in_c[bad_one] = 1;
for (int j = be[bad_one].first; j != bad_one; j = be[j].first) {
in_c[j] = 1;
}
int mind = inf;
for (int i = 0; i < n; ++i) {
if (!in_c[i]) continue;
for (auto p : ag[i]) {
if (!used[p.first]) continue;
mind = min(mind, p.second - be[i].second);
}
}
cout << sum + mind << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
3 5 6 1 2 4 1 3 2 2 3 0 3 4 1 4 5 1 5 2 1 4 4 1 2 4 1 3 6 1 4 8 4 2 1000000 3 3 1 2 100 2 1 10 2 3 1000
output:
5 18 1100
result:
ok 3 number(s): "5 18 1100"
Test #2:
score: 0
Accepted
time: 51ms
memory: 3572kb
input:
50000 4 5 2 4 998973548 2 3 501271695 4 1 778395982 1 4 32454891 1 2 757288934 4 5 1 4 720856669 2 3 665098951 3 4 407461517 2 1 866914401 1 2 457859826 4 5 1 2 75288664 1 4 624893594 3 2 458973866 2 4 769074655 2 3 834773751 4 5 2 3 237060634 2 4 297307882 3 4 200383586 1 2 42856502 3 1 16574713 4 ...
output:
1291015520 1530420294 1534956009 480300722 1366795927 1541095843 2493849488 858095911 1034153425 793861088 605832428 1051598350 612891589 1265994009 517769091 1678219738 1556463491 93634961 960978736 984886788 1696503797 1002892611 1969660290 1431417780 1515267731 977157479 1937478556 654475526 1401...
result:
ok 50000 numbers
Test #3:
score: -100
Wrong Answer
time: 66ms
memory: 3876kb
input:
50000 4 6 1 3 754771977 2 3 517886121 1 4 392356144 1 2 702785740 3 4 888230940 2 1 829304957 4 6 2 4 255940037 1 2 380616616 1 4 819140865 3 4 36965607 1 3 496378345 4 3 652252309 4 6 2 4 179216787 4 2 401136502 1 2 715271531 1 3 859345710 3 4 24470489 1 4 148650889 4 6 3 2 20348069 1 2 152861663 1...
output:
1613028005 913960568 1284952701 1294564551 199037829 1236121455 983447828 1161647829 1289612543 2444304029 431872921 1272140390 949528400 2328941976 696541797 363553357 999320657 2221495861 879052116 1287531701 912524980 1072419431 1187727045 1571845059 1184110956 1136184594 430092563 1132894799 962...
result:
wrong answer 313th numbers differ - expected: '1326090611', found: '1821468187'