QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721095 | #5548. Increase the Toll Fees | wjt# | RE | 22ms | 16532kb | C++14 | 2.6kb | 2024-11-07 15:12:46 | 2024-11-07 15:12:47 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 100005
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int n, m, fa[N], cnt;
struct edge {
int u, v, w;
bool tag;
bool operator < (const edge& t) const { return w < t.w; };
}e[N];
int find(int u) {
return fa[u] == u ? u : fa[u] = find(fa[u]);
}
vector <edge> pre;
void clear() {
for (int i = 1; i <= n; i++)
fa[i] = i;
cnt = 0;
}
struct node {
int v, w;
};
vector <node> son[N];
int f[N][20], Max[N][20];
int dep[N], val[N];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for (int i = 1; (1 << i) <= dep[u]; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i].v, w = son[u][i].w;
if (v == fa) continue;
val[v] = w;
dfs(v, u);
}
}
void fun(int u, int fa) {
Max[u][0] = val[u];
for (int i = 1; i <= 19; i++) {
Max[u][i] = max(Max[ f[u][i - 1] ][i - 1], Max[u][i - 1]);
}
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i].v;
if (v != fa) fun(v, u);
}
}
int get(int s, int t) {
int res = -INF;
if (dep[s] < dep[t]) swap(s, t);
for (int i = 19; i >= 0; i--) {
if (dep[s] - (1 << i) >= dep[t]) {
res = max(res, Max[s][i]);
s = f[s][i];
}
}
if (s == t) return res;
for (int i = 19; i >= 0; i--) {
if (f[s][i] != f[t][i]) {
res = max(res, max(Max[s][i], Max[t][i]) );
s = f[s][i];
t = f[t][i];
}
}
return max(res, max(Max[s][0],Max[t][0]));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].tag = 1;
}
sort(e + 1, e + m + 1);
clear();
for (int i = 1; i <= m; i++) {
int u = e[i].u, v = e[i].v;
int fu = find(u), fv = find(v);
if (fu == fv) continue;
fa[fv] = fu;
e[i].tag = 0;
pre.push_back(e[i]);
cnt++;
if (cnt == n - 1) break;
}
clear();
for (int i = 1; i <= m; i++) {
if (!e[i].tag) continue;
int u = e[i].u, v = e[i].v;
int fu = find(u), fv = find(v);
if (fu == fv) continue;
fa[fv] = fu;
son[u].push_back({ v,e[i].w });
son[v].push_back({ u,e[i].w });
cnt++;
if (cnt == n - 1) break;
}
if (cnt < n - 1) {
cout << -1;
return 0;
}
int rt = 1;
dfs(rt, 0);
val[rt] = -INF;
fun(rt, 0);
ll ans = 0;
for (int i = 0; i < pre.size(); i++) {
int s = pre[i].u, t = pre[i].v;
//cout << s << " " << t << " " << pre[i].w << " ";
ll tmp = (ll)get(s, t);
//cout << tmp << " " << endl;
ans += tmp + 1LL - pre[i].w;
}
cout << ans;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9820kb
input:
4 6 1 2 2 1 3 5 1 4 5 2 3 3 2 4 5 3 4 4
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7752kb
input:
3 4 1 2 3 2 3 4 1 3 5 1 3 10
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9752kb
input:
5 10 1 2 14 1 3 14 1 4 9 1 5 15 2 3 8 2 3 10 2 4 13 3 4 8 4 5 10 4 5 15
output:
21
result:
ok single line: '21'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7816kb
input:
2 1 1 2 1
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 22ms
memory: 16532kb
input:
29171 100000 7223 21138 270743473 5598 27967 847631606 12666 26050 847631606 75 15747 270743473 8522 12955 847631606 6069 23750 270743473 18708 22605 847631606 16814 22169 847631606 11550 27119 847631606 562 15959 847631606 9400 11110 270743473 15325 23805 270743473 19169 24404 270743473 6649 12062 ...
output:
16827826868780
result:
ok single line: '16827826868780'
Test #6:
score: -100
Runtime Error
input:
47977 200000 10970 47321 440845807 1166 29708 767952745 319 37520 546280762 17581 29425 558321466 22079 26884 344816304 7479 44260 791002634 14685 44163 837529020 1537 10359 330017953 8634 27064 969738917 32950 37192 728271930 34751 42782 63025978 32540 34226 86057211 36786 46050 826927874 30444 436...