oj.uz

Submission #559642

# Submission time Handle Problem Language Result Execution time Memory
559642 2022-05-10T10:53:36 Z fcmalkcin Road Closures (APIO21_roads) C++17
5 / 100
 436 ms 109748 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=5e5+50;
const ll mod=1e9+7  ;
const ll base=1e18;

#include "roads.h"

/// i believe myself
/// goal 0/7

set<pll> adj[maxn];
pll anc[maxn];
struct tk
{
    vector<pll> st;
    vector<ll> vt;
    ll n;
    void setup()
    {
        n=vt.size();
        st=vector<pll> (4*n+5, {0,0});
    }
    pll mer(pll a,pll b)
    {
        return make_pair(a.ff+b.ff,a.ss+b.ss);
    }
    void update(ll id,ll left,ll right,ll x)
    {
        if (x>right||x<left)
            return ;
        if (left==right)
        {
            st[id].ff+=1;
            st[id].ss+=vt[left-1];
            return ;
        }
        ll mid=(left+right)/2;
        update(id*2,left,mid,x);
        update(id*2+1,mid+1,right,x);
        st[id]=mer(st[id*2],st[id*2+1]);
    }
    void update1(ll pos)
    {
        pos=lower_bound(vt.begin(),vt.end(),pos)-vt.begin()+1;
        update(1,1,n,pos);
    }
    pll get(ll id,ll left,ll right,ll x,ll y)
    {
        if (x>right||y<left)
            return make_pair(0,0);
        if (x<=left&&y>=right)
            return st[id];
        ll mid=(left+right)/2;
        return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
    }
    ll get1(ll id,ll left,ll right,ll p)
    {
        if (left==right)
            return left;
        ll mid=(left+right)/2;
        if (st[id*2].ff>=p)
            return get1(id*2,left,mid,p);
        return get1(id*2+1,mid+1,right,p-st[id*2].ff);
    }
    ll get2(ll p)
    {
        if (p==0)
            return 0;
        ll pos=get1(1,1,n,p);
        auto h=get(1,1,n,1,pos);
        return h.ss-(h.ff-p)*vt[pos-1];
    }
};
tk gr[maxn];
ll cnt=0;
ll f[maxn];
bool dd[maxn];
ll sl[maxn];

void dfs(ll u,ll par)
{
    cnt++;
    f[u]=cnt;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        if (to==par)
            continue;
        anc[to]=make_pair(u,p.ss);
        dfs(to,u);
        gr[u].vt.pb(p.ss);
    }
    sort(gr[u].vt.begin(),gr[u].vt.end());
    gr[u].vt.resize(unique(gr[u].vt.begin(),gr[u].vt.end())-gr[u].vt.begin());
    gr[u].setup();
}
set<pll> st;
void ers(ll u)
{
    st.erase(make_pair(f[u],u));
    for (auto to:adj[u])
    {
        ll h=to.ff;
        ll w=to.ss;
        adj[h].erase(make_pair(u,w));
    }
    gr[anc[u].ff].update1(anc[u].ss);
    sl[anc[u].ff]++;
}
ll dp[maxn][2];
ll k;
void dfs1(ll u,ll par,ll w)
{
    dp[u][0]=base;
    dp[u][1]=base;
    dd[u]=1;
    vector<ll> vt;
    ll cntnw=0;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (to==par)
            continue;
        dfs1(to,u,w);
        cntnw+=dp[to][0];
        if (dp[to][0]>dp[to][1])
        {
            vt.pb(dp[to][1]-dp[to][0]);
        }
    }
    sort(vt.begin(),vt.end());
    ll pre=cntnw;
    for (int i=-1; i<min(k,(ll)vt.size()); i++)
    {
        if (i!=-1)
        {
            cntnw+=vt[i];
        }
        ll slnw=i+1+sl[u];
        ll h=max((ll)0,slnw-k);
        dp[u][0]=min(dp[u][0],cntnw+gr[u].get2(h)+w);
    }
    cntnw=pre;
    for (int i=-1; i<min(k,(ll)vt.size()); i++)
    {
        if (i!=-1)
        {
            cntnw+=vt[i];
        }
        ll slnw=i+2+sl[u];
        ll h=max((ll)0,slnw-k);
        if (h<=sl[u])
            dp[u][1]=min(dp[u][1],cntnw+gr[u].get2(h));
    }
}
vector<ll> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W)
{
    ll n=N;
    vector<pll> vt;
    for (int i=0; i<U.size(); i++)
    {
        adj[U[i]+1].insert(make_pair(V[i]+1,W[i]));
        adj[V[i]+1].insert(make_pair(U[i]+1,W[i]));
    }
    for (int i=1; i<=n; i++)
    {
        vt.pb(make_pair(adj[i].size(),i));
    }
    sort(vt.begin(),vt.end());
    dfs(1,0);
    for (int i=1; i<=n; i++)
        st.insert(make_pair(f[i],i));
    ll id=0;
    vector<ll> res;
    for (int t=0; t<=n-1; t++)
    {
        k=t;
        while (id<vt.size()&&vt[id].ff<=t)
        {
            ll pos=vt[id].ss;
            ers(pos);
         //   cout <<pos<<" "<<t<<" chk1"<<endl;
            id++;
        }
        ll ans=0;
        for (auto to:st)
        {
            if (dd[to.ss])
                continue;
            dfs1(to.ff,0,0);
            ans+=dp[to.ff][0];
        }
        res.pb(ans);
        for (auto to:st)
        {
            dd[to.ss]=0;
        }
    }
    return res;
}

/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    vector<ll> p,p1,p2;
    cin>> n;
    for (int i=1;i<=n-1;i++)
    {
        ll x, y, w;
        cin>> x>> y>> w;
        p.pb(x);
        p1.pb(y);
        p2.pb(w);
    }
    vector<ll> res=minimum_closure_costs(n, p,p1,p2);
    for (auto to:res) cout <<to<<" ";
}*/

/*5
0 1 1
0 2 4
0 3 3
2 4 2
*/

Compilation message

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for (int i=0; i<U.size(); i++)
      |                   ~^~~~~~~~~
roads.cpp:189:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         while (id<vt.size()&&vt[id].ff<=t)
      |                ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51276 KB Output is correct
2 Correct 27 ms 51984 KB Output is correct
3 Correct 29 ms 52124 KB Output is correct
4 Correct 30 ms 52168 KB Output is correct
5 Correct 27 ms 51160 KB Output is correct
6 Correct 26 ms 51204 KB Output is correct
7 Correct 24 ms 51216 KB Output is correct
8 Correct 26 ms 51852 KB Output is correct
9 Correct 27 ms 51996 KB Output is correct
10 Correct 25 ms 51284 KB Output is correct
11 Correct 25 ms 51304 KB Output is correct
12 Correct 145 ms 73568 KB Output is correct
13 Correct 293 ms 88180 KB Output is correct
14 Correct 283 ms 89644 KB Output is correct
15 Correct 327 ms 93892 KB Output is correct
16 Correct 315 ms 94452 KB Output is correct
17 Correct 253 ms 88272 KB Output is correct
18 Correct 31 ms 51148 KB Output is correct
19 Correct 209 ms 84796 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51200 KB Output is correct
2 Incorrect 159 ms 109748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51156 KB Output is correct
2 Correct 30 ms 51276 KB Output is correct
3 Correct 34 ms 51196 KB Output is correct
4 Incorrect 26 ms 51176 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51156 KB Output is correct
2 Correct 30 ms 51276 KB Output is correct
3 Correct 34 ms 51196 KB Output is correct
4 Incorrect 26 ms 51176 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 436 ms 93260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 436 ms 93260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51276 KB Output is correct
2 Correct 27 ms 51984 KB Output is correct
3 Correct 29 ms 52124 KB Output is correct
4 Correct 30 ms 52168 KB Output is correct
5 Correct 27 ms 51160 KB Output is correct
6 Correct 26 ms 51204 KB Output is correct
7 Correct 24 ms 51216 KB Output is correct
8 Correct 26 ms 51852 KB Output is correct
9 Correct 27 ms 51996 KB Output is correct
10 Correct 25 ms 51284 KB Output is correct
11 Correct 25 ms 51304 KB Output is correct
12 Correct 145 ms 73568 KB Output is correct
13 Correct 293 ms 88180 KB Output is correct
14 Correct 283 ms 89644 KB Output is correct
15 Correct 327 ms 93892 KB Output is correct
16 Correct 315 ms 94452 KB Output is correct
17 Correct 253 ms 88272 KB Output is correct
18 Correct 31 ms 51148 KB Output is correct
19 Correct 209 ms 84796 KB Output is correct
20 Correct 26 ms 51200 KB Output is correct
21 Incorrect 159 ms 109748 KB Output isn't correct
22 Halted 0 ms 0 KB -