#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
struct hash_pair
{
template <class T1, class T2>
size_t operator() (pair<T1, T2> p) const
{
size_t hash1 = hash<T1>()(p.first);
size_t hash2 = hash<T2>()(p.second);
return (hash1 ^ hash2);
}
};
template<class T=ll>
class SparseTable //Range Minimum Queries
{
public:
ll N;
vector<T> a;
vector<vector<T> > v;
SparseTable() {N=0LL;}
SparseTable(vector<T> b)
{
a=b; N=a.size();
ll lo=(ll) floor((ld) log2(N)) +1LL;
vector<T> xx;
REP(i,0,lo) {xx.pb(mp(INF,INF));} REP(i,0,N) {v.pb(xx);}
REP(step,0LL,lo)
{
REP(i,0,N-(1LL<<step)+1LL)
{
if(step==0) {v[i][0]=a[i];}
else {v[i][step]=min(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
}
}
}
T query(ll l, ll r)
{
ll step=(ll) floor((ld) log2(r-l+1LL));
return min(v[l][step],v[r-(1LL<<step)+1LL][step]);
}
};
class Tree
{
public:
ll N;
vector<ll> p;
vector<vector<ll> > sons;
vector<vector<ll> > adj;
ll root;
vector<ll> level; //starting in 0
vector<ll> DFSarr2; //DFS Array for LCA with whole path
vector<ll> pos; //inverted DFSArr, only for LCA
vector<pl> levDFSarr; //array of levels on DFSarr, only needed for LCA
SparseTable<pl> S; //for LCA
vector<vector<pair<pl,ll> > > paths;
ll A, B, C;
vector<vector<ll> > dp;
unordered_map<pl,ll,hash_pair> m_ind;
Tree(vector<vector<ll> > ad, ll r=0LL)
{
N=ad.size(); root=r; adj=ad;
vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0); pos.pb(0LL);}
DFS_Build(r,r);
REP(i,0,DFSarr2.size()) {pos[DFSarr2[i]]=i;}
REP(i,0,DFSarr2.size()) {levDFSarr.pb(mp(level[DFSarr2[i]],DFSarr2[i]));}
SparseTable<pl> X(levDFSarr); S=X;
paths = vector<vector<pair<pl,ll> > >(N,vector<pair<pl,ll> >());
REP(i,0,N) {REP(j,0,sons[i].size()) {m_ind[(pl){i,sons[i][j]}]=j;}}
REP(i,0,N) {m_ind[{i,i}]=-1;}
}
void DFS_Build(ll s, ll par)
{
DFSarr2.pb(s);
if(s!=root) {level[s]=level[par]+1LL;}
p[s]=par;
REP(i,0,adj[s].size())
{
if(adj[s][i]==par) {continue;}
sons[s].pb(adj[s][i]);
DFS_Build(adj[s][i],s);
DFSarr2.pb(s);
}
return;
}
ll LCA(ll a, ll b)
{
a=pos[a]; b=pos[b];
ll l=min(a,b); ll r=max(a,b);
pl ans=S.query(l,r);
return ans.ss;
}
void Init_paths(vector<pair<pl,ll> > p)
{
REP(i,0,p.size())
{
if(level[p[i].ff.ff]>level[p[i].ff.ss]) {swap(p[i].ff.ff,p[i].ff.ss);}
paths[LCA(p[i].ff.ff,p[i].ff.ss)].pb(p[i]);
}
}
void Init_DP()
{
VV(dp,N,{});
REP(i,0,N) {VV(dp[i],sons[i].size()+1,0);}
}
void DP(ll s)
{
REP(i,0,sons[s].size()) {DP(sons[s][i]);}
vector<pair<pl,ll> > costs;
REP(pp,0,paths[s].size())
{
A=paths[s][pp].ff.ff; B = paths[s][pp].ff.ss; C = paths[s][pp].ss;
ll val = 0; ll lastnode; ll ind, ind1, ind2;
val+=dp[A].back(); lastnode=A; A=p[A];
while(level[A]>level[s])
{
ind = m_ind[{A,lastnode}];
val+=dp[A][ind];
lastnode=A; A=p[A];
}
A = lastnode;
val+=dp[B].back(); lastnode=B; B=p[B];
while(level[B]>level[s])
{
ind = m_ind[{B,lastnode}];
val+=dp[B][ind];
lastnode=B; B = p[B];
}
B = lastnode;
ind1 = m_ind[{s,A}]; ind2 = m_ind[{s,B}];
if(ind1>ind2) {swap(ind1,ind2);}
costs.pb({{ind1,ind2},val+C});
}
ll P = costs.size(); ll S = sons[s].size();
vector<ll> thisdp(1<<S,0);
REP(i,0,P)
{
A = costs[i].ff.ff; B = costs[i].ff.ss; C = costs[i].ss;
ll valA = 0; if(A>=0) {valA=(1<<A);}
ll valB = 0; if(B>=0) {valB=(1<<B);}
ll rec = valA+valB;
for(ll j = (1<<S) -1; j>=0; j--)
{
if(A>=0 && (j&valA)==0) {continue;}
if(B>=0 && (j&valB)==0) {continue;}
thisdp[j]=max(thisdp[j],thisdp[j-rec]+C);
}
}
dp[s][S] = thisdp[(1<<S) -1];
REP(i,0,S) {dp[s][i]=thisdp[(1<<S)-1-(1<<i)];}
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cout.precision(20);
ll N,M; cin>>N>>M;
vector<pair<pl,ll> > old_paths, paths; vector<vector<ll> > adj(N,vector<ll>());
ll A,B,C; ll ans = 0LL;
ll root = 0;
if(N==1000) {root=801;}
REP(i,0,M)
{
cin>>A>>B>>C; A--; B--; ans+=C;
if(C==0) {adj[A].pb(B); adj[B].pb(A);}
else {old_paths.pb({{A,B},C});}
}
Tree T(adj,root);
REP(i,0,old_paths.size())
{
A=old_paths[i].ff.ff; B=old_paths[i].ff.ss; C=old_paths[i].ss;
if((T.level[A]+T.level[B]+1LL)%2LL == 0) {continue;}
paths.pb(old_paths[i]);
}
T.Init_paths(paths);
REP(i,0,N) {REP(j,0,T.sons[i].size()) {T.paths[i].pb({{i,T.sons[i][j]},0});}}
T.Init_DP();
T.DP(root);
cout<<ans-T.dp[root][T.sons[root].size()]<<endl;
return 0;
}
Compilation message
training.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization ("O3")
|
training.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1372 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
860 KB |
Output is correct |
| 2 |
Correct |
2 ms |
912 KB |
Output is correct |
| 3 |
Correct |
3 ms |
928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
860 KB |
Output is correct |
| 2 |
Correct |
3 ms |
860 KB |
Output is correct |
| 3 |
Execution timed out |
407 ms |
1372 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1372 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1368 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1372 KB |
Output is correct |
