#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
typedef tuple<int, int, int> t3;
struct node{
node(){}
node(int x){
idx = x;
rev = val = 0; mx = Pi(0, x);
child[0] = child[1] = par = pp = 0;
}
Pi mx;
int val, idx, rev;
node *child[2], *par, *pp;
inline int mydir(){
return par->child[1] == this;
}
inline void pushdown(){
if(rev){
swap(child[0], child[1]);
if(child[0])child[0]->rev ^= 1;
if(child[1])child[1]->rev ^= 1;
rev = 0;
}
}
inline void pushup(){
mx.Fi = val, mx.Se = idx;
if(child[0] && child[0]->mx.Fi > mx.Fi)mx = child[0]->mx;
if(child[1] && child[1]->mx.Fi > mx.Fi)mx = child[1]->mx;
}
void rotate(int dir){
node *c = child[!dir];
c->pushdown();
if(par)par->child[mydir()] = c; c->par = par;
if(pp)c->pp = pp, pp = 0;
child[!dir] = c->child[dir];
if(c->child[dir])c->child[dir]->par = this;
c->child[dir] = this;
par = c;
pushup();
c->pushup();
}
void splay(node *rootp){
while(par != rootp){
if(par->par == rootp){
par->pushdown();
par->rotate(!mydir());
}
else{
par->par->pushdown();
par->pushdown();
int md = mydir();
if(par->mydir() != md){
par->rotate(!md);
par->rotate(md);
}
else{
par->par->rotate(!md);
par->rotate(!md);
}
}
}
}
};
node *mem[1000010];
pii meme[1000040];
void access(node *v){
v->splay(0); v->pushdown();
if(v->child[1]){
v->child[1]->par = 0, v->child[1]->pp = v;
v->child[1] = 0; v->pushup();
}
while(v->pp){
node *u = v->pp;
u->splay(0); u->pushdown();
if(u->child[1])u->child[1]->par = 0, u->child[1]->pp = u;
u->child[1] = v;
v->par = u; v->pp = 0;
u->pushup();
v->splay(0);
}
}
void makeroot(node *v){
access(v);
v->rev ^= 1;
v->pushdown();
}
int mz;
void link(int ux, int vx, int L){
node *u = mem[ux];
node *v = mem[vx];
makeroot(v);
++mz; mem[mz] = new node(mz);
mem[mz]->val = L; mem[mz]->mx.Fi = L;
meme[mz] = Pi(ux, vx);
access(u);
u->child[1] = mem[mz]; mem[mz]->par = u;
mem[mz]->child[1] = v; v->par = mem[mz];
mem[mz]->pushup(); u->pushup();
// printf("link %d -- %d, %d\n", ux, mz, L); printf("link %d -- %d, %d\n", vx, mz, L);
}
void link2(int ux, int vx){
node *u = mem[ux];
node *v = mem[vx];
makeroot(v);
access(u);
u->child[1] = v; v->par = u;
v->pushup(); u->pushup();
}
void cut(int ux, int vx){
node *u = mem[ux];
node *v = mem[vx];
access(u);
v->splay(0);
if(v->pp == u)v -> pp = 0;
else{
v->pushdown();
v->child[1] = 0;
v->pushup();
u->par = 0;
}
// printf("cut %d -- %d\n", ux, vx);
}
/*
void link(int uv, int vv, int L){
node *u = mem[uv], *v = mem[vv];
makeroot(v);
++mz; mem[mz] = new node(mz);
mem[mz]->val = L; mem[mz]->mx.Fi = L;
meme[mz] = Pi(uv, vv);
access(u);
u->child[1] = mem[mz]; mem[mz]->par = u;
mem[mz]->child[1] = v; v->par = mem[mz];
mem[mz]->pushup(); u->pushup();
}
void cut(int uv, int vv){
node *u = mem[uv], *v = mem[vv];
access(u);
v->splay(0);
if(v->pp == u){
v->pp = 0;
}
else{
v->pushdown();
v->child[1] = 0;
v->pushup();
u->par = 0;
}
}
void query(int x, int y, int l){
node *u = mem[x], *v = mem[y];
access(u);
access(v);
u->splay(0);
Pi res;
if(u->pp){
res = u->mx;
if(u->pp != v){
node *w = u->pp;
w->splay(0); w->pushdown();
if(res.Fi < w->val)res = Pi(w->val, w->idx);
if(res.Fi < w->child[1]->mx.Fi)res = w->child[1]->mx;
}
}
else{
res = Pi(u->val, u->idx);
u->pushdown();
if(res.Fi < u->child[1]->mx.Fi)res = u->child[1]->mx;
}
if(res.Fi <= l)return;
ans -= res.Fi;
ans += l;
cut(res.Se, meme[res.Se].Fi);
cut(res.Se, meme[res.Se].Se);
link(x, y, l);
}
*/
int N, M;
vector <pii> E[100010];
ll ans;
int p[100010];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }
void query(int x, int y, int l, ll &tans, pii &rr){
// printf("Q%d %d\n", x, y);
node *u = mem[x], *v = mem[y];
access(u);
access(v);
u->splay(0);
Pi res;
if(u->pp){
res = u->mx;
if(u->pp != v){
node *w = u->pp;
w->splay(0); w->pushdown();
if(res.Fi < w->val)res = Pi(w->val, w->idx);
if(res.Fi < w->child[1]->mx.Fi)res = w->child[1]->mx;
}
}
else{
res = Pi(u->val, u->idx);
u->pushdown();
if(res.Fi < u->child[1]->mx.Fi)res = u->child[1]->mx;
}
tans -= res.Fi;
cut(res.Se, meme[res.Se].Fi);
cut(res.Se, meme[res.Se].Se);
rr = res;
link2(x, y);
}
const int INF = -1e9-10;
inline void getInt(int &a){
a = 0;
char c;
while(!isdigit(c = getchar()));
a = c - '0';
while(isdigit(c = getchar())){
a = a * 10 + c - '0';
}
}
void solve(){
getInt(N); getInt(M);
vector <t3> V;
rep(i, M){
int x, y, z; getInt(x); getInt(y); getInt(z);
if(x == y) continue;
E[x].pb(pii(z, y));
E[y].pb(pii(z, x));
V.emplace_back(z, x, y);
}
mz = N;
sort(all(V));
for(int i=1;i<=N;i++)p[i] = i;
for(int i=1;i<=N;i++)mem[i] = new node(i);
for(int i=0;i<sz(V);i++){
t3 &a = V[i];
int x = Find(get<1>(a)), y = Find(get<2>(a));
if(x != y){
p[x] = y, ans += get<0>(a);
int u = get<1>(a), v = get<2>(a);
if(u > v)swap(u, v);
link(u, v, get<0>(a));
}
}
for(int i=1;i<=N;i++){
ll tans = ans;
vector <t3> W;
rep(j, sz(E[i])){
auto &e = E[i][j];
tans += e.Fi;
pii rr;
query(i, e.Se, INF, tans, rr);
int L = rr.Fi, x = meme[rr.Se].Fi, y = meme[rr.Se].Se;
W.emplace_back(x, y, L);
}
rep(j, sz(E[i])){
cut(i, E[i][j].Se);
}
for(t3 &e : W) link(get<0>(e), get<1>(e), get<2>(e));
printf("%lld\n", tans);
}
}
int main(){
int Tc = 1; //scanf("%d\n", &Tc);
for(int tc=1;tc<=Tc;tc++){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
21064 KB |
Output is correct |
| 2 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 3 |
Correct |
6 ms |
21068 KB |
Output is correct |
| 4 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 5 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 6 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 7 |
Correct |
13 ms |
21064 KB |
Output is correct |
| 8 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 9 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 10 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 11 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 12 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 13 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 14 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 15 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 16 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 17 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 18 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 19 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 20 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 21 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 22 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 23 |
Correct |
6 ms |
21064 KB |
Output is correct |
| 24 |
Correct |
9 ms |
21064 KB |
Output is correct |
| 25 |
Correct |
0 ms |
20388 KB |
Output is correct |
| 26 |
Correct |
0 ms |
20388 KB |
Output is correct |
| 27 |
Correct |
0 ms |
20388 KB |
Output is correct |
| 28 |
Correct |
3 ms |
20652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
85348 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
