oj.uz

Submission #498701

# Submission time Handle Problem Language Result Execution time Memory
498701 2021-12-26T07:48:53 Z Carmel_Ab1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 668 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")

//#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];

pl t[4096];
ll lz[4096];
int sz=4096;

inline void init(){
    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){return t[1];}

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=qur(1,n+1);

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

    while(cur!=s){
        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;
    clear();
    for(int i=0; i<=n; i++)
        w_up[i]=0;
    dfs(s,-1);

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

    ll ans=0;

    for(int i=0; i<k; i++) {
        ll x=upd(s);
        if(!x)break;
        ans+=x;
    }

    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;
    init();


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

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 13 ms 496 KB Output is correct
4 Correct 15 ms 496 KB Output is correct
5 Correct 10 ms 488 KB Output is correct
6 Correct 15 ms 460 KB Output is correct
7 Correct 16 ms 460 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 13 ms 496 KB Output is correct
4 Correct 15 ms 496 KB Output is correct
5 Correct 10 ms 488 KB Output is correct
6 Correct 15 ms 460 KB Output is correct
7 Correct 16 ms 460 KB Output is correct
8 Correct 339 ms 532 KB Output is correct
9 Correct 418 ms 572 KB Output is correct
10 Correct 450 ms 564 KB Output is correct
11 Correct 260 ms 668 KB Output is correct
12 Correct 370 ms 664 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 13 ms 496 KB Output is correct
4 Correct 15 ms 496 KB Output is correct
5 Correct 10 ms 488 KB Output is correct
6 Correct 15 ms 460 KB Output is correct
7 Correct 16 ms 460 KB Output is correct
8 Correct 339 ms 532 KB Output is correct
9 Correct 418 ms 572 KB Output is correct
10 Correct 450 ms 564 KB Output is correct
11 Correct 260 ms 668 KB Output is correct
12 Correct 370 ms 664 KB Output is correct
13 Execution timed out 1079 ms 588 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 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 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 13 ms 496 KB Output is correct
4 Correct 15 ms 496 KB Output is correct
5 Correct 10 ms 488 KB Output is correct
6 Correct 15 ms 460 KB Output is correct
7 Correct 16 ms 460 KB Output is correct
8 Correct 339 ms 532 KB Output is correct
9 Correct 418 ms 572 KB Output is correct
10 Correct 450 ms 564 KB Output is correct
11 Correct 260 ms 668 KB Output is correct
12 Correct 370 ms 664 KB Output is correct
13 Execution timed out 1079 ms 588 KB Time limit exceeded
14 Halted 0 ms 0 KB -