#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll ma[4*N],tag[4*N],n,x,y,c,m,ans;
vector<pll> st[N],ed[N];
vector<pair<pll,ll> > one;
void push(ll id){
if(tag[id]){
tag[(id<<1)]+=tag[id];
tag[(id<<1)+1]+=tag[id];
ma[(id<<1)]+=tag[id];
ma[(id<<1)+1]+=tag[id];
tag[id]=0;
}
}
void add(ll id,ll l,ll r,ll ql,ll qr,ll del){
if(l>=ql&&r<=qr){ma[id]+=del;tag[id]+=del;return ;}
if(l>=qr||r<=ql)return ;
ll mid=(l+r)>>1;
push(id);
add((id<<1),l,mid,ql,qr,del);
add((id<<1)+1,mid,r,ql,qr,del);
ma[id]=max(ma[(id<<1)],ma[(id<<1)+1]);
}
ll q(ll id,ll l,ll r,ll to){
if(l==r-1){return ma[id];}
ll mid=(l+r)>>1;
push(id);
if(to<mid){
return q(id<<1,l,mid,to);
}else{
return q((id<<1)+1,mid,r,to);
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
REP(i,m){
cin>>x>>y>>c;
if(y<x)swap(y,x);
add(1,1,n+1,x,y,c);
st[x].pb(mp(y,c));
ed[y].pb(mp(x,c));
one.pb(mp(mp(x,y),c));
}
//REP1(j,n)cout<<q(1,1,n+1,j)<<(j==n?"\n":" ");
ans=ma[1];
//cout<<ma[1]<<"\n";
REP1(i,n){
for(auto j:st[i]){
add(1,1,n+1,1,n+1,j.Y);
add(1,1,n+1,i,j.X,2*-j.Y);
}
for(auto j:ed[i]){
add(1,1,n+1,1,n+1,-j.Y);
add(1,1,n+1,j.X,i,2*j.Y);
}
ans=min(ans,ma[1]);
}
for(auto i:one){
add(1,1,n+1,1,n+1,i.Y);
add(1,1,n+1,i.X.X,i.X.Y,2*-i.Y);
ans=min(ans,ma[1]);
add(1,1,n+1,1,n+1,-i.Y);
add(1,1,n+1,i.X.X,i.X.Y,2*i.Y);
}
cout<<ans<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
