Submission #282675

#	Time	Username	Problem	Language	Result	Execution time	Memory
282675		doowey	Wiring (IOI17_wiring)	C++14	100 / 100	66 ms	14568 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const ll inf = (ll)1e18;


ll min_total_length(vector<int> r, vector<int> b) {
    vector<pii> al;
    al.push_back(mp(-1, -1));
    for(auto x : r)
        al.push_back(mp(x, 0));
    for(auto x : b)
        al.push_back(mp(x, 1));
    sort(al.begin(), al.end());
    int sz = al.size();
    vector<ll> dp(sz);
    vector<ll> sa(sz);
    vector<ll> sb(sz);
    vector<ll> low(sz);
    vector<ll> pfi(sz);
    for(int i = 1; i < sz; i ++ ){
        dp[i] = inf;
    }
    vector<int> cur[2];
    ll tq;
    ll ccb = 0;
    ll pq;
    int now;
    int csz;
    ll go;
    ll extra;
    ll niz;
    ll diff;
    for(int i = 1; i < sz; i ++ ){
        if(al[i].se != al[i-1].se){
            cur[0].clear();
            swap(cur[0], cur[1]);
            pq = inf;
            for(auto x : cur[0]){
                sa[x]=al[cur[0].back()].fi - al[x].fi;
            }
            for(int i = cur[0].size() - 1; i >= 0 ; i -- ){
                if(i < cur[0].size() - 1)
                    sa[cur[0][i]] += sa[cur[0][i+1]];
                low[cur[0][i]] = sa[cur[0][i]] + dp[cur[0][i] - 1];
            }
            diff = al[i].fi - al[i - 1].fi;
            for(int i = 0 ; i < cur[0].size(); i ++ ){
                niz = cur[0].size() - i;
                pfi[cur[0][i]] = dp[cur[0][i]-1] + sa[cur[0][i]] + diff * 1ll * niz;
                if(i)
                    pfi[cur[0][i]]=min(pfi[cur[0][i]],pfi[cur[0][i-1]]);
            }
            go = 0;
            now = (int)cur[0].size() - 1;
        }
        cur[1].push_back(i);
        sb[i]=al[i].fi-al[cur[1][0]].fi;
        go += sb[i];
        if(!cur[0].empty()){
            dp[i] = dp[i - 1] + al[i].fi - al[cur[0].back()].fi;
            if(now >= 0)
                pq = min(pq, low[cur[0][now--]]);
            csz = cur[1].size();
            dp[i] = min(dp[i],go + pq + csz * 1ll * (al[cur[1][0]].fi - al[cur[0].back()].fi));
            if(now >= 0)
                dp[i] = min(dp[i], pfi[cur[0][now]] + go);
        }
    }
    return dp[sz - 1];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 if(i < cur[0].size() - 1)
      |                    ~~^~~~~~~~~~~~~~~~~~~
wiring.cpp:57:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(int i = 0 ; i < cur[0].size(); i ++ ){
      |                             ~~^~~~~~~~~~~~~~~
wiring.cpp:34:8: warning: unused variable 'tq' [-Wunused-variable]
   34 |     ll tq;
      |        ^~
wiring.cpp:35:8: warning: unused variable 'ccb' [-Wunused-variable]
   35 |     ll ccb = 0;
      |        ^~~
wiring.cpp:40:8: warning: unused variable 'extra' [-Wunused-variable]
   40 |     ll extra;
      |        ^~~~~
wiring.cpp:68:12: warning: 'go' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |         go += sb[i];
wiring.cpp:72:44: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |                 pq = min(pq, low[cur[0][now--]]);
      |                                         ~~~^~

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