Submission #992110

#	Time	Username	Problem	Language	Result	Execution time	Memory
992110		PedroBigMan	Training (IOI07_training)	C++14	91 / 100	423 ms	1496 KiB

training

#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=501;}
    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 (stderr)

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")
      |

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 0 / 9
• Subtask 11: 9 / 9