Submission #498697

#	Time	Username	Problem	Language	Result	Execution time	Memory
498697		Carmel_Ab1	Paths (RMI21_paths)	C++17	36 / 100	1076 ms	844 KiB

Main

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}

const int maxn=2001;

vpl g[maxn];
int n,k;

int timer=0;

int tin[maxn],tout[maxn],up[maxn];
ll w_up[maxn];

struct seg{
    pl t[4096];
    ll lz[4096];
    int sz=4096;

    seg(){}
    seg(int n){
        for(int i=sz/2; i<sz; i++)
            t[i].second=i-sz/2;
    }

    inline void clear(){
        for(int i=0; i<sz; i++){
            t[i].first=t[i].second=0;
            lz[i]=0;
        }
    }
    inline void set_who(int i,int v){
        t[i+sz/2].second=v;
    }
    inline void add(int x,ll v){
        t[x].first+=v;
        lz[x]+=v;
    }
    inline void push(int x){
        add(2*x,lz[x]);
        add(2*x+1,lz[x]);
        lz[x]=0;
    }

    inline void upd(int a,int b,int l,int r,int x,ll v){
        if(b<=l || r<=a)
            return;
        else if(a<=l && r<=b){
            add(x,v);
            return;
        }
        push(x);

        int m=(l+r)/2;
        upd(a,b,l,m,2*x,v);
        upd(a,b,m,r,2*x+1,v);

        t[x]=max(t[2*x],t[2*x+1]);
    }

    inline void upd(int a,int b,ll v){
        upd(a,b,0,sz/2,1,v);
    }

    inline pl qur(int a,int b,int l,int r,int x){
        if(b<=l || r<=a)
            return {-1,-1};
        else if(a<=l && r<=b)
            return t[x];
        push(x);
        int m=(l+r)/2;

        return max(
                qur(a,b,l,m,2*x),
                qur(a,b,m,r,2*x+1));
    }
    pl qur(int a,int b){
        return qur(a,b,0,sz/2,1);
    }
};

seg ST;
inline void dfs(int src,int par){
    tin[src]=++timer;
    up[src]=par;
    for(pl nbr:g[src])
        if(nbr.first!=par) {
            dfs(nbr.first, src);
            w_up[nbr.first]=nbr.second;
        }
    tout[src]=timer;
}



inline ll upd(ll s){

    pl mx=ST.qur(1,n+1);

    ll ans=mx.first;
    ll cur=mx.second;

    while(cur!=s){
        ST.upd(tin[cur],tout[cur]+1,-w_up[cur]);
        w_up[cur]=0;
        ll p=up[cur];
        up[cur]=s;
        cur=p;
    }
    return ans;
}
inline ll calc(ll s){

    timer=0;
    ST.clear();
    for(int i=0; i<=n; i++)
        w_up[i]=0;
    dfs(s,-1);

    for(int i=1; i<=n; i++)
        ST.set_who(tin[i],i);
    for(int i=1; i<=n; i++)
        ST.upd(tin[i],tout[i]+1,w_up[i]);

    ll ans=0;

    for(int i=0; i<k; i++)
        ans+=upd(s);

    return ans;
}
void solve() {
    cin >> n >> k;
    for(int i=0; i<n-1; i++){
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    for(int i=1; i<=n; i++)
        tin[i]=tout[i]=up[i]=w_up[i]=0;

    ST=seg(n+2);

    for(int i=1; i<=n; i++)
        cout << calc(i) << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'void usaco(std::string)':
Main.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32