Submission #624895

#	Time	Username	Problem	Language	Result	Execution time	Memory
624895		Lobo	Road Closures (APIO21_roads)	C++17	24 / 100	26 ms	8360 KiB

roads

#include<iostream>
#include<vector>
#include<cassert>
#include<algorithm>
#include "roads.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x)  int32_t(x.size())
#define int long long
const int maxn = 2e3+10;
const int inf = 1e18+10;
const int mnv = -1e15-10;
const int mxv = 1e15+10;
int n, dp[maxn][2], mark[maxn], atv[maxn];
vector<int> g[maxn], gr[maxn];
vector<pair<int,int>> gesp[maxn];

int cnt[maxn];
vector<int> trq[maxn], trs[maxn], f1[maxn], f2[maxn];
//add/remove pos from id
int att(int no, int l, int r, int id, int pos, int val) {
    // cout << " " << no << " " << l << " " << r << endl;
    if(l > pos || r < pos) return no;
    if(no == 0) {
        no = ++cnt[id]; 
    }
    //trq[id][trq[id].size()-1]
    while(no >= sz(f1[id])) {
        trq[id].pb(0);
        trs[id].pb(0);
        f1[id].pb(0);
        f2[id].pb(0);
    }
    if(l == r) {
        assert(no < sz(trq[id]));
        trq[id][no]+= val;
        assert(no < sz(trs[id]));
        trs[id][no]+= val*pos;
        return no;
    }
    int mid = (l+r)>>1;
    // cout << no << " -> " << f1[id][no] << endl;
    // int abc;
    // f1[id][no] = abc = att(f1[id][no],l,mid,id,pos,val);

    // assert(no < sz(f1[id]));
    // f1[id][no] = att(f1[id][no],l,mid,id,pos,val);

    // int wtf = f1[id][no];
    // f1[id][no] = att(wtf,l,mid,id,pos,val);

    int aux;
    aux = att(f1[id][no],l,mid,id,pos,val);
    f1[id][no] = aux;
    aux = att(f2[id][no],mid+1,r,id,pos,val);
    f2[id][no] = aux;
    // f1[id][no] = att(f1[id][no],l,mid,id,pos,val);
    // f2[id][no] = att(f2[id][no],mid+1,r,id,pos,val);
    trq[id][no] = trq[id][f1[id][no]]+trq[id][f2[id][no]];
    trs[id][no] = trs[id][f1[id][no]]+trs[id][f2[id][no]];
    // cout << " " << no << " " << l << " " << r << " " << trq[id][no] << " " << pos  << " " << f1[id][no] << " " << f2[id][no] << endl;

    // cout << aux << endl;
    // cout << no << " <- " << f1[id][no] << endl;
    // cout << no << endl;
    return no;
}

int find(int no, int l, int r, int id, int val) {
    // cout << no << " " << l << " " << r << " " << trq[id][no] << " " << trs[id][no] << " " << val << endl;
    //quero pegar os val menores caras em (l,r)
    if(no == 0) return 0;
    if(l == r) {
        // cout << l << " " << val << endl;
        return val*r;
    }

    int mid = (l+r)>>1;
    if(trq[id][f1[id][no]] >= val) return find(f1[id][no],l,mid,id,val);
    else return trs[id][f1[id][no]]+find(f2[id][no],mid+1,r,id,val-trq[id][f1[id][no]]);
}

void dfs(int u, int qtd, int ant) {
    mark[u] = 1;
    int ans = 0;
    vector<int> use;
    for(auto V : gesp[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        dfs(v,qtd,u);
        ans+= min(dp[v][0],dp[v][1]+w);
        use.pb(-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w);
        att(1,mnv,mxv,u,-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w,1);
    }
    // sort(all(use));
    //se nao tem a aresta com o pai -> sz(g[u])-1-qtd = t
    dp[u][0] = dp[u][1] = inf;
    if(sz(g[u])-qtd-1 <= 0) dp[u][1] = ans;
    else dp[u][1] = ans+find(1,mnv,mxv,u,sz(g[u])-qtd-1);
    if(sz(g[u])-qtd <= 0) dp[u][0] = ans;
    else dp[u][0] = ans+find(1,mnv,mxv,u,sz(g[u])-qtd);
    // cout << "  " << u << " " << qtd << " " << sz(g[u]) << " " << ans << " " << find(1,mnv,mxv,u,sz(g[u])-qtd) << endl;
    for(auto x : use) {
        att(1,mnv,mxv,u,x,-1);
    }
    // for(int i = 1; i <= sz(g[u])-qtd; i++) {
    //     ans+= use[i-1];
    //     if(i == sz(g[u])-qtd-1) dp[u][1] = ans;
    //     if(i == sz(g[u])-qtd) dp[u][0] = ans;
    // }
}

std::vector<int> minimum_closure_costs(int32_t N, std::vector<int32_t> U,std::vector<int32_t> V,std::vector<int32_t> W) {
    n = N;
    vector<int> ans;
    int sumw = 0;
    for(int i = 0; i < n-1; i++) {
        int u = U[i];
        int v = V[i];
        int w = W[i];
        sumw+= w;
        g[u].pb(i);
        g[v].pb(i);
        // gesp[u].pb(mp(v,w));
        // gesp[v].pb(mp(u,w));
    }
    for(int i = 0; i < n; i++) {
        cnt[i] = 1;
        gr[sz(g[i])].pb(i);
        // trq[i].resize(60*maxn);
        // trs[i].resize(60*maxn);
        // f1[i].resize(60*maxn);
        // f2[i].resize(60*maxn);
    }

    vector<int> esp;
    for(int k = n-1; k >=1; k--) {
        for(auto i : gr[k]) {
            atv[i] = 1;
            // cout << i << endl;
            esp.pb(i);
            for(auto id : g[i]) {
                int v = i^U[id]^V[id];
                int w = W[id];
                if(atv[v]) {
                    gesp[i].pb(mp(v,w));    
                    gesp[v].pb(mp(i,w)); 
                    att(1,mnv,mxv,v,w,-1);   
                }
                else {
                    // cout << " " << i << " " << v << " " << w << endl;
                    att(1,mnv,mxv,i,w,1);
                }
            }
        }
        // att(1,mnv,mxv,0,40,1);
        // cout << " - " << find(1,mnv,mxv,0,1) << endl;

        int ans1 = 0;
        for(auto x : esp) {
            if(!mark[x]) {
                // cout << x << " " << x << endl;
                dfs(x,k,-1);
                ans1+= dp[x][0];
            }
        }
        // dfs(0,k,-1);
        ans.pb(ans1);

        for(auto v : esp) {
            mark[v] = 0;
        }

    }
    ans.pb(sumw);
    reverse(all(ans));

    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22