oj.uz

Submission #559637

# Submission time Handle Problem Language Result Execution time Memory
559637 2022-05-10T10:45:43 Z fcmalkcin Road Closures (APIO21_roads) C++17
5 / 100
 481 ms 112660 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)+w);
    }
}
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);
            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 29 ms 51196 KB Output is correct
2 Correct 29 ms 52008 KB Output is correct
3 Correct 30 ms 52092 KB Output is correct
4 Correct 36 ms 51916 KB Output is correct
5 Correct 27 ms 51156 KB Output is correct
6 Correct 28 ms 51288 KB Output is correct
7 Correct 28 ms 51280 KB Output is correct
8 Correct 41 ms 51848 KB Output is correct
9 Correct 29 ms 51972 KB Output is correct
10 Correct 27 ms 51188 KB Output is correct
11 Correct 28 ms 51276 KB Output is correct
12 Correct 164 ms 73900 KB Output is correct
13 Correct 270 ms 89124 KB Output is correct
14 Correct 325 ms 91128 KB Output is correct
15 Correct 342 ms 95488 KB Output is correct
16 Correct 377 ms 96140 KB Output is correct
17 Correct 270 ms 89864 KB Output is correct
18 Correct 31 ms 51208 KB Output is correct
19 Correct 228 ms 85472 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 51220 KB Output is correct
2 Correct 32 ms 51204 KB Output is correct
3 Correct 26 ms 51132 KB Output is correct
4 Incorrect 29 ms 51340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 51220 KB Output is correct
2 Correct 32 ms 51204 KB Output is correct
3 Correct 26 ms 51132 KB Output is correct
4 Incorrect 29 ms 51340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 25.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 51196 KB Output is correct
2 Correct 29 ms 52008 KB Output is correct
3 Correct 30 ms 52092 KB Output is correct
4 Correct 36 ms 51916 KB Output is correct
5 Correct 27 ms 51156 KB Output is correct
6 Correct 28 ms 51288 KB Output is correct
7 Correct 28 ms 51280 KB Output is correct
8 Correct 41 ms 51848 KB Output is correct
9 Correct 29 ms 51972 KB Output is correct
10 Correct 27 ms 51188 KB Output is correct
11 Correct 28 ms 51276 KB Output is correct
12 Correct 164 ms 73900 KB Output is correct
13 Correct 270 ms 89124 KB Output is correct
14 Correct 325 ms 91128 KB Output is correct
15 Correct 342 ms 95488 KB Output is correct
16 Correct 377 ms 96140 KB Output is correct
17 Correct 270 ms 89864 KB Output is correct
18 Correct 31 ms 51208 KB Output is correct
19 Correct 228 ms 85472 KB Output is correct
20 Correct 26 ms 51156 KB Output is correct
21 Incorrect 182 ms 112660 KB Output isn't correct
22 Halted 0 ms 0 KB -