oj.uz

Submission #624892

# Submission time Handle Problem Language Result Execution time Memory
624892 2022-08-09T00:49:45 Z Lobo Road Closures (APIO21_roads) C++17
14 / 100
 2000 ms 6336 KB 
#include<iostream>
#include<vector>
#include<cassert>
#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];
vector<int> g[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);

    // auto 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;
        // trq[i].resize(60*maxn);
        // trs[i].resize(60*maxn);
        // f1[i].resize(60*maxn);
        // f2[i].resize(60*maxn);
    }

    ans.pb(sumw);
    for(int k = 1; k <= n-1; k++) {
        vector<int> esp;
        for(int i = 0; i < n; i++) {
            if(g[i].size() > k) {
                // cout << i << endl;
                esp.pb(i);
                for(auto id : g[i]) {
                    int v = i^U[id]^V[id];
                    int w = W[id];
                    if(g[v].size() > k) {
                        gesp[i].pb(mp(v,w));    
                    }
                    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(int i = 0; i < n; i++) {
            mark[i] = 0;
            gesp[i].clear();
            if(g[i].size() > k) {
                for(auto id : g[i]) {
                    int v = i^U[id]^V[id];
                    int w = W[id];
                    if(g[v].size() <= k) {
                        att(1,mnv,mxv,i,w,-1);
                    }
                }
            }
        }

    }

    return ans;
}

Compilation message

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:142:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  142 |             if(g[i].size() > k) {
      |                ~~~~~~~~~~~~^~~
roads.cpp:148:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  148 |                     if(g[v].size() > k) {
      |                        ~~~~~~~~~~~~^~~
roads.cpp:175:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  175 |             if(g[i].size() > k) {
      |                ~~~~~~~~~~~~^~~
roads.cpp:179:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  179 |                     if(g[v].size() <= k) {
      |                        ~~~~~~~~~~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Execution timed out 2071 ms 2124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Runtime error 28 ms 5292 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 10 ms 640 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 5 ms 1108 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 42 ms 780 KB Output is correct
14 Correct 92 ms 940 KB Output is correct
15 Correct 85 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 4 ms 852 KB Output is correct
19 Correct 67 ms 620 KB Output is correct
20 Correct 76 ms 616 KB Output is correct
21 Correct 1 ms 468 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 10 ms 640 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 5 ms 1108 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 42 ms 780 KB Output is correct
14 Correct 92 ms 940 KB Output is correct
15 Correct 85 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 4 ms 852 KB Output is correct
19 Correct 67 ms 620 KB Output is correct
20 Correct 76 ms 616 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 20 ms 4036 KB Output is correct
24 Correct 42 ms 6336 KB Output is correct
25 Correct 30 ms 3052 KB Output is correct
26 Correct 114 ms 2360 KB Output is correct
27 Correct 1460 ms 3316 KB Output is correct
28 Correct 1274 ms 788 KB Output is correct
29 Correct 38 ms 5588 KB Output is correct
30 Correct 243 ms 3844 KB Output is correct
31 Correct 190 ms 1256 KB Output is correct
32 Execution timed out 2085 ms 816 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 5588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 5588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Execution timed out 2071 ms 2124 KB Time limit exceeded
3 Halted 0 ms 0 KB -