#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define befv(V) ((V)[sz(V)-2])
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const bool debug = 0;
const int MAXN = 100005;
const int MAXM = 300005;
vector<pii> Bumsoo[MAXN];
vector<int> G[MAXN], T[MAXN];
int prt[17][MAXN], prtmxe[17][MAXN];
int dep[MAXN], cnt[MAXN], dfo[MAXN];
int A[MAXM], B[MAXM], C[MAXM], O[MAXM];
int ud[MAXN], isD[MAXN], isDn;
bitset<MAXM> isE;
ll MSTC;
int N, M;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
int lca(int a, int b) {
if(dep[a] > dep[b]) swap(a, b);
const int dt = dep[b] - dep[a];
for(int i = 0; i < 17; i++) if(dt & (1<<i)) b = prt[i][b];
if(a == b) return a;
for(int i = 17; i--;) if(prt[i][a] != prt[i][b]) {
a = prt[i][a]; b = prt[i][b];
}
return prt[0][a];
}
int upmxe(int i, int l) {
int ret = 0;
for(int j = 0; j < 17; j++) if(l & (1<<j)) {
upmax(ret, prtmxe[j][i]);
i = prt[j][i];
}
return ret;
}
void f(int i, int &c) {
cnt[i] = 1; dfo[i] = ++c;
for(int e : T[i]) {
int v = A[e] + B[e] - i;
if(dep[v]) continue;
prt[0][v] = i;
prtmxe[0][v] = C[e];
dep[v] = dep[i] + 1;
f(v, c);
cnt[i] += cnt[v];
}
}
pll dfs(int idx) {
auto &V = Bumsoo[idx];
if(V.empty()) {
pll ret = (isD[idx] == isDn) ? pll(-INFLL, 0) : pll(0, -INFLL);
if(debug) printf("DFS idx=%d : %lld / %lld\n", idx, ret.first, ret.second);
return ret;
}
pll ret(0, 0); ll mx = -INFLL;
if(isD[idx] == isDn) ret.first = -INFLL;
for(auto &e : V) {
pll t = dfs(e.first);
if(isD[idx] != isDn) {
ll q = max(t.first, t.second + e.second);
ret.first += q;
ret.second += q;
upmax(mx, -q + t.second);
} else {
ret.second += max(t.first, t.second + e.second);
}
upmax(ret.first, -INFLL);
upmax(ret.second, -INFLL);
upmin(ret.first, INFLL);
upmin(ret.second, INFLL);
}
if(isD[idx] != isDn) ret.second += mx;
upmax(ret.first, -INFLL);
upmax(ret.second, -INFLL);
upmin(ret.first, INFLL);
upmin(ret.second, INFLL);
if(debug) printf("DFS idx=%d : %lld / %lld\n", idx, ret.first, ret.second);
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 1; i <= M; i++) {
cin >> A[i] >> B[i] >> C[i];
G[A[i]].eb(i);
G[B[i]].eb(i);
}
iota(O, O+M+1, 0); sort(O+1, O+M+1, [&](int a, int b) { return C[a] < C[b]; });
iota(ud, ud+N+1, 0);
for(int oi = 1, i; oi <= M; oi++) {
i = O[oi];
if(uf(A[i]) == uf(B[i])) continue;
uf(A[i], B[i]);
isE[i] = true;
MSTC += C[i];
}
for(int i = 1; i <= M; i++) if(isE[i]) {
T[A[i]].eb(i);
T[B[i]].eb(i);
}
dep[1] = 1; { int c = 0; f(1, c); }
for(int j = 1; j < 17; j++) for(int i = 1; i <= N; i++) {
prt[j][i] = prt[j-1][prt[j-1][i]];
prtmxe[j][i] = max(prtmxe[j-1][i], prtmxe[j-1][prt[j-1][i]]);
}
iota(ud, ud+N+1, 0);
for(int i = 1; i <= N; i++) {
vector<int> V;
ll ret = MSTC; isDn++;
isD[i] = isDn; V.eb(i);
for(int e : G[i]) {
int v = A[e] + B[e] - i;
ret += C[e];
isD[v] = isDn;
V.eb(v);
}
sort(allv(V), [&](int a, int b) { return dfo[a] < dfo[b]; });
vector<pii> PV;
for(int i = 1, n = sz(V); i < n; i++) PV.eb(lca(V[i-1], V[i]), i);
sort(allv(PV), [&](pii a, pii b) { return dfo[a.first] > dfo[b.first]; });
for(auto &e : PV) {
int p, a, b;
tie(p, a) = e;
b = V[a]; a = V[a-1];
a = uf(a); b = uf(b);
if(a != p) {
Bumsoo[p].eb(a, upmxe(a, dep[a] - dep[p]));
uf(p, a);
if(debug) printf("ADD %d-%d : %d\n", a, p, upmxe(a, dep[a]-dep[p]));
}
if(b != p) {
Bumsoo[p].eb(b, upmxe(b, dep[b] - dep[p]));
uf(p, b);
if(debug) printf("ADD %d-%d : %d\n", b, p, upmxe(b, dep[b]-dep[p]));
}
}
if(debug) {
printf("i=%d : ", i);
for(int v : V) printf("%d ", v);
puts("");
for(auto &e : PV) printf("(%d,%d) ", e.first, e.second);
puts("");
printf("%d / ret = %lld\n", PV.back().first, dfs(PV.back().first).second);
}
if(!PV.empty()) ret -= dfs(PV.back().first).second;
printf("%lld\n", ret);
for(int v : V) {
ud[v] = v;
Bumsoo[v].clear();
}
for(auto &e : PV) {
int v = e.first;
ud[v] = v;
Bumsoo[v].clear();
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
7928 KB |
Output is correct |
| 2 |
Correct |
16 ms |
7928 KB |
Output is correct |
| 3 |
Correct |
18 ms |
7960 KB |
Output is correct |
| 4 |
Correct |
18 ms |
7960 KB |
Output is correct |
| 5 |
Correct |
17 ms |
8088 KB |
Output is correct |
| 6 |
Correct |
16 ms |
8088 KB |
Output is correct |
| 7 |
Correct |
15 ms |
8088 KB |
Output is correct |
| 8 |
Correct |
17 ms |
8264 KB |
Output is correct |
| 9 |
Correct |
16 ms |
8356 KB |
Output is correct |
| 10 |
Correct |
17 ms |
8356 KB |
Output is correct |
| 11 |
Correct |
15 ms |
8356 KB |
Output is correct |
| 12 |
Correct |
14 ms |
8356 KB |
Output is correct |
| 13 |
Correct |
13 ms |
8356 KB |
Output is correct |
| 14 |
Correct |
16 ms |
8356 KB |
Output is correct |
| 15 |
Correct |
20 ms |
8356 KB |
Output is correct |
| 16 |
Correct |
14 ms |
8356 KB |
Output is correct |
| 17 |
Correct |
14 ms |
8356 KB |
Output is correct |
| 18 |
Correct |
15 ms |
8356 KB |
Output is correct |
| 19 |
Correct |
15 ms |
8356 KB |
Output is correct |
| 20 |
Correct |
17 ms |
8356 KB |
Output is correct |
| 21 |
Correct |
15 ms |
8356 KB |
Output is correct |
| 22 |
Correct |
16 ms |
8356 KB |
Output is correct |
| 23 |
Correct |
17 ms |
8356 KB |
Output is correct |
| 24 |
Correct |
18 ms |
8356 KB |
Output is correct |
| 25 |
Correct |
9 ms |
8356 KB |
Output is correct |
| 26 |
Correct |
11 ms |
8356 KB |
Output is correct |
| 27 |
Correct |
11 ms |
8356 KB |
Output is correct |
| 28 |
Correct |
12 ms |
8356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1933 ms |
46184 KB |
Output is correct |
| 2 |
Correct |
1979 ms |
52724 KB |
Output is correct |
| 3 |
Execution timed out |
2083 ms |
57156 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
