oj.uz

Submission #498700

# Submission time Handle Problem Language Result Execution time Memory
498700 2021-12-26T07:46:30 Z Carmel_Ab1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 588 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,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);
}

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 484 KB Output is correct
4 Correct 17 ms 460 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 16 ms 496 KB Output is correct
7 Correct 14 ms 492 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 484 KB Output is correct
4 Correct 17 ms 460 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 16 ms 496 KB Output is correct
7 Correct 14 ms 492 KB Output is correct
8 Correct 377 ms 548 KB Output is correct
9 Correct 432 ms 588 KB Output is correct
10 Correct 414 ms 560 KB Output is correct
11 Correct 302 ms 540 KB Output is correct
12 Correct 352 ms 540 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 484 KB Output is correct
4 Correct 17 ms 460 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 16 ms 496 KB Output is correct
7 Correct 14 ms 492 KB Output is correct
8 Correct 377 ms 548 KB Output is correct
9 Correct 432 ms 588 KB Output is correct
10 Correct 414 ms 560 KB Output is correct
11 Correct 302 ms 540 KB Output is correct
12 Correct 352 ms 540 KB Output is correct
13 Execution timed out 1068 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 484 KB Output is correct
4 Correct 17 ms 460 KB Output is correct
5 Correct 10 ms 460 KB Output is correct
6 Correct 16 ms 496 KB Output is correct
7 Correct 14 ms 492 KB Output is correct
8 Correct 377 ms 548 KB Output is correct
9 Correct 432 ms 588 KB Output is correct
10 Correct 414 ms 560 KB Output is correct
11 Correct 302 ms 540 KB Output is correct
12 Correct 352 ms 540 KB Output is correct
13 Execution timed out 1068 ms 588 KB Time limit exceeded
14 Halted 0 ms 0 KB -