oj.uz

Submission #926582

# Submission time Handle Problem Language Result Execution time Memory
926582 2024-02-13T11:16:02 Z adhityamv Road Closures (APIO21_roads) C++17
5 / 100
 2000 ms 64524 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<ll,ll>
#define fi first
#define se second
const ll INF=1000000000;
const ll K=200000;
ll seg[4*K]={};
ll lazy[4*K]={};
void Build(ll l,ll r,ll pos){
    if(l==r){
        seg[pos]=0;
        lazy[pos]=INF;
        return;
    }
    ll m=(l+r)/2;
    Build(l,m,2*pos);
    Build(m+1,r,2*pos+1);
    seg[pos]=seg[2*pos]+seg[2*pos+1];
    lazy[pos]=INF;
}
void UpdateLazy(ll l,ll r,ll pos){
    if(lazy[pos]==INF) return;
    seg[pos]=(r-l+1LL)*lazy[pos];
    if(l!=r){
        lazy[2*pos]=lazy[pos];
        lazy[2*pos+1]=lazy[pos];
    }
    lazy[pos]=INF;
}
void Update(ll l,ll r,ll pos,ll ql,ll qr,ll qval){
    if(ql>qr) return;
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return;
    if(ql<=l && qr>=r){
        lazy[pos]=qval;
        UpdateLazy(l,r,pos);
        return;
    }
    ll m=(l+r)/2;
    Update(l,m,2*pos,ql,qr,qval);
    Update(m+1,r,2*pos+1,ql,qr,qval);
    seg[pos]=(seg[2*pos]+seg[2*pos+1]);
}
ll Query(ll l,ll r,ll pos, ll ql,ll qr){
    if(ql>qr) return 0;
    UpdateLazy(l,r,pos);
    if(ql>r || qr<l) return 0;
    if(ql<=l && qr>=r){
        return seg[pos];
    }
    ll m=(l+r)/2;
    return (Query(l,m,2*pos,ql,qr)+Query(m+1,r,2*pos+1,ql,qr));
}
const ll N=100000;
vector<pii> edges[N];
vector<ll> et;
ll n,m;
ll deg[N];
ll depth[N];
ll focc[N];
ll locc[N];
ll parent[N];
ll upweight[N];
void euler_tour(ll u,ll p){
    parent[u]=p;
    focc[u]=et.size();
    et.push_back(u);
    for(auto v:edges[u]){
        if(v.fi==p) continue;
        depth[v.fi]=depth[u]+1;
        upweight[v.fi]=v.se;
        euler_tour(v.fi,u);
        et.push_back(u);
    }
    locc[u]=et.size()-1;
}
vector<ll> bydeg[N];
multiset<ll> allnums[N];
multiset<ll>  topk[N];
multiset<ll> topk1[N];
ll dp[N];
ll dp1[N];
void dfs(ll u,ll p){
    dp[u]=dp1[u]=0;
    for(auto v:edges[u]){
        if(v.fi==p) continue;
        dfs(v.fi,u);
        allnums[u].insert(upweight[v.fi]+dp1[v.fi]-dp[v.fi]);
        dp[u]+=dp[v.fi];
        dp1[u]+=dp[v.fi];
    }
    auto it=allnums[u].end();
    if(it!=allnums[u].begin()){
        it--;
        topk[u].insert(*it);
        dp[u]+=max(*it,0LL);
        allnums[u].erase(it);
    }
}
ll k=2;
void updatepp(){
    vector<pii> needupdate;
    for(ll i:bydeg[k]) needupdate.push_back(mp(depth[i],i));
    for(ll i:bydeg[k]){
        if(i==0) continue;
        if(deg[parent[i]]>=k) continue;
        needupdate.push_back(mp(depth[parent[i]],parent[i]));
    }
    sort(needupdate.begin(),needupdate.end(),greater<pii>());
    for(auto pa:needupdate){
        ll u=pa.se;
        ll orval=dp[u];
        ll orval1=dp1[u];
        if(topk1[u].size()!=topk[u].size()){
            dp1[u]+=max(*topk[u].begin(),0LL);
            topk1[u].insert(*topk[u].begin());
        }
        if(!allnums[u].empty()){
            auto it=allnums[u].end();
            it--;
            dp[u]+=max(*it,0LL);
            topk[u].insert(*it);
            allnums[u].erase(it);
        }
        ll ex=Query(0,m-1,1,focc[u],locc[u]);
        dp[u]+=ex;
        dp1[u]+=ex;
        if(u==0) continue;
        if(deg[u]<k){
            Update(0,m-1,1,focc[u],locc[u],0);
            Update(0,m-1,1,focc[u],focc[u],dp[u]-orval);
        } else{
            ll p=parent[u];
            ll val=upweight[u]+orval1-orval;
            bool w=false;
            bool w1=false;
            if(topk1[p].find(val)!=topk1[p].end()){
                topk[p].erase(topk[p].find(val));
                topk1[p].erase(topk1[p].find(val));
                dp[p]-=max(val,0LL);
                dp1[p]-=max(val,0LL);
            } else if(topk[p].find(val)!=topk[p].end()){
                 topk[p].erase(topk[p].find(val));
                 dp[p]-=max(val,0LL);
            } else{
                allnums[p].erase(allnums[p].find(val));
            }
            val=upweight[u]+dp1[u]-dp[u];
            topk[p].insert(val);
            dp[p]+=max(val,0LL);
            topk1[p].insert(val);
            dp1[p]+=max(val,0LL);
            if(topk[p].size()>=k){
                auto it=topk[p].begin();
                allnums[p].insert(*it);
                dp[p]-=max(*it,0LL);
                topk[p].erase(it);
            }
            if(topk1[p].size()>=k-1){
                dp1[p]-=max(*topk1[p].begin(),0LL);
                topk1[p].erase(topk1[p].begin());
            }
        }
    }
    Update(0,m-1,1,0,n-1,0);
    k++;
}
vector<ll> minimum_closure_costs(int nn,vector<int> u,vector<int> v,vector<int> w){
    n=nn;
    ll tot=0;
    for(ll i=0;i<n-1;i++){
        edges[u[i]].push_back(mp(v[i],w[i]));
        edges[v[i]].push_back(mp(u[i],w[i]));
        deg[u[i]]++,deg[v[i]]++;
        tot+=w[i];
    }
    depth[0]=0;
    euler_tour(0,-1);
    m=et.size();
    vector<ll> ans;
    ans.push_back(tot);
    dfs(0,-1);
    ans.push_back(tot-dp[0]);
    for(ll i=0;i<n;i++){
        for(ll j=0;j<=deg[i];j++) bydeg[j].push_back(i);
    }
    Build(0,m-1,1);
    while(k<n){
        updatepp();
        ans.push_back(tot-dp[0]);
    }
    return ans;
}

Compilation message

roads.cpp: In function 'void updatepp()':
roads.cpp:156:30: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  156 |             if(topk[p].size()>=k){
      |                ~~~~~~~~~~~~~~^~~
roads.cpp:162:31: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  162 |             if(topk1[p].size()>=k-1){
      |                ~~~~~~~~~~~~~~~^~~~~
roads.cpp:138:18: warning: unused variable 'w' [-Wunused-variable]
  138 |             bool w=false;
      |                  ^
roads.cpp:139:18: warning: unused variable 'w1' [-Wunused-variable]
  139 |             bool w1=false;
      |                  ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 7 ms 29532 KB Output is correct
3 Correct 7 ms 29532 KB Output is correct
4 Correct 7 ms 29532 KB Output is correct
5 Correct 5 ms 29016 KB Output is correct
6 Correct 5 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 7 ms 29532 KB Output is correct
9 Correct 7 ms 29528 KB Output is correct
10 Correct 5 ms 29108 KB Output is correct
11 Correct 5 ms 29020 KB Output is correct
12 Correct 69 ms 48144 KB Output is correct
13 Correct 114 ms 61828 KB Output is correct
14 Correct 118 ms 60220 KB Output is correct
15 Correct 129 ms 62468 KB Output is correct
16 Correct 145 ms 62888 KB Output is correct
17 Correct 122 ms 62980 KB Output is correct
18 Correct 5 ms 29020 KB Output is correct
19 Correct 102 ms 59512 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Execution timed out 2098 ms 64524 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Runtime error 33 ms 58716 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Runtime error 33 ms 58716 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 55616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 55616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 7 ms 29532 KB Output is correct
3 Correct 7 ms 29532 KB Output is correct
4 Correct 7 ms 29532 KB Output is correct
5 Correct 5 ms 29016 KB Output is correct
6 Correct 5 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 7 ms 29532 KB Output is correct
9 Correct 7 ms 29528 KB Output is correct
10 Correct 5 ms 29108 KB Output is correct
11 Correct 5 ms 29020 KB Output is correct
12 Correct 69 ms 48144 KB Output is correct
13 Correct 114 ms 61828 KB Output is correct
14 Correct 118 ms 60220 KB Output is correct
15 Correct 129 ms 62468 KB Output is correct
16 Correct 145 ms 62888 KB Output is correct
17 Correct 122 ms 62980 KB Output is correct
18 Correct 5 ms 29020 KB Output is correct
19 Correct 102 ms 59512 KB Output is correct
20 Correct 5 ms 29020 KB Output is correct
21 Execution timed out 2098 ms 64524 KB Time limit exceeded
22 Halted 0 ms 0 KB -