oj.uz

Submission #498696

# Submission time Handle Problem Language Result Execution time Memory
498696 2021-12-26T07:38:34 Z Carmel_Ab1 Paths (RMI21_paths) C++17
36 / 100
 430 ms 688 KB 
#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=1001;

vpl g[maxn];
int n,k;

int timer=0;

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

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

    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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 16 ms 420 KB Output is correct
4 Correct 14 ms 412 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 18 ms 460 KB Output is correct
7 Correct 14 ms 456 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 16 ms 420 KB Output is correct
4 Correct 14 ms 412 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 18 ms 460 KB Output is correct
7 Correct 14 ms 456 KB Output is correct
8 Correct 378 ms 504 KB Output is correct
9 Correct 430 ms 544 KB Output is correct
10 Correct 417 ms 536 KB Output is correct
11 Correct 292 ms 460 KB Output is correct
12 Correct 333 ms 520 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 16 ms 420 KB Output is correct
4 Correct 14 ms 412 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 18 ms 460 KB Output is correct
7 Correct 14 ms 456 KB Output is correct
8 Correct 378 ms 504 KB Output is correct
9 Correct 430 ms 544 KB Output is correct
10 Correct 417 ms 536 KB Output is correct
11 Correct 292 ms 460 KB Output is correct
12 Correct 333 ms 520 KB Output is correct
13 Runtime error 1 ms 688 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 16 ms 420 KB Output is correct
4 Correct 14 ms 412 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 18 ms 460 KB Output is correct
7 Correct 14 ms 456 KB Output is correct
8 Correct 378 ms 504 KB Output is correct
9 Correct 430 ms 544 KB Output is correct
10 Correct 417 ms 536 KB Output is correct
11 Correct 292 ms 460 KB Output is correct
12 Correct 333 ms 520 KB Output is correct
13 Runtime error 1 ms 688 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -