Submission #171662

#	Time	Username	Problem	Language	Result	Execution time	Memory
171662		alexandra_udristoiu	Wiring (IOI17_wiring)	C++14	100 / 100	43 ms	9336 KiB

wiring

#include<iostream>
#include<vector>
#include "wiring.h"
#define DIM 200005
#define f first
#define s second
using namespace std;
static long long d[DIM], sp[DIM];
pair<int, int> v[DIM];
pair<int, long long> dq[DIM];
long long min_total_length(vector<int> r, vector<int> b) {
    int n, m, i, j, curr, prv, ind, p, u;
    long long sum1, sum2, minim;
    n = r.size();
    m = b.size();
    i = j = 0;
    while(i < n && j < m){
        if(r[i] < b[j]){
            v[i + j + 1] = make_pair(r[i], 0);
            i++;
        }
        else{
            v[i + j + 1] = make_pair(b[j], 1);
            j++;
        }
    }
    for(; i < n; i++){
        v[i + j + 1] = make_pair(r[i], 0);
    }
    for(; j < m; j++){
        v[i + j + 1] = make_pair(b[j], 1);
    }
    n += m;
    for(i = 1; i <= n; i++){
        sp[i] = sp[i - 1] + v[i].f;
    }
    prv = 1;
    sum1 = v[1].f;
    sum2 = 0;
    for(i = 2; i <= n; i++){
        if(v[i].s != v[i - 1].s){
            curr = i;
            break;
        }
        else{
            d[i] = 1000000000000000000LL;
            sum1 += v[i].f;
        }
    }
    for(; i <= n; i++){
        sum2 += v[i].f;
        d[i] = sum2 - sum1;
        if(i - curr + 1 < curr - prv){
            d[i] += ( (curr - prv) - (i - curr + 1) ) * 1LL * v[curr].f;
        }
        else{
            d[i] -= ( (i - curr + 1) - (curr - prv) ) * 1LL * v[curr - 1].f;
        }
        if(v[i + 1].s != v[i].s){
            break;
        }
    }
    for(i = i + 1; i <= n; i++){
        if(v[i - 1].s != v[i].s){
            prv = curr;
            curr = i;
            p = 1;
            u = 0;
            for(j = i - 1; j >= prv; j--){
                if(d[j - 1] == 0){
                    break;
                }
                sum1 = d[j - 1] - sp[i - 1] + sp[j - 1] + v[i].f * 1LL * (i - j);
                while(p <= u && dq[u].s > sum1){
                    u--;
                }
                dq[++u] = make_pair(j, sum1);
            }
            minim = min(d[i - 1], d[i - 2]) + v[i].f - v[i - 1].f;
            if(dq[p].f == i - 1){
                p++;
            }
            if(p <= u){
                d[i] = min(minim, dq[p].s);
            }
            else{
                d[i] = minim;
            }
            ind = i - 1;
        }
        else{
            minim += v[i].f - v[curr - 1].f;
            if(i - curr + 1 <= curr - prv){
                ind--;
                minim = min(minim, d[ind - 1] + sp[i] - sp[curr - 1] - sp[curr - 1] + sp[ind - 1]);
                if(dq[p].f == ind){
                    p++;
                }
            }
            if(p <= u){
                d[i] = min(minim, dq[p].s + sp[i] - sp[curr] - v[curr].f * 1LL * (i - curr) );
            }
            else{
                d[i] = minim;
            }
        }
    }
    return d[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:92:19: warning: 'minim' may be used uninitialized in this function [-Wmaybe-uninitialized]
             minim += v[i].f - v[curr - 1].f;
                   ^
wiring.cpp:100:13: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(p <= u){
             ^~
wiring.cpp:5:11: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
 #define f first
           ^~~~~
wiring.cpp:12:37: note: 'p' was declared here
     int n, m, i, j, curr, prv, ind, p, u;
                                     ^
wiring.cpp:95:42: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 minim = min(minim, d[ind - 1] + sp[i] - sp[curr - 1] - sp[curr - 1] + sp[ind - 1]);
                                      ~~~~^~~
wiring.cpp:69:30: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
             for(j = i - 1; j >= prv; j--){
                            ~~^~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45