Submission #209460

#	Time	Username	Problem	Language	Result	Execution time	Memory
209460		balbit	Sky Walking (IOI19_walk)	C++14	24 / 100	2236 ms	683700 KiB

walk

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ALL(x) x.begin(),x.end()
#define SZ(x) x.size()
#define pb push_back


#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ",_do(__VA_ARGS__)
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT


const int maxn = 1e6;

struct Br{
    int l,r,y;
};
struct Bd{
    int x, y;
};

#define pli pair<ll, int>
#define pii pair<int, int>
#define f first
#define s second

vector<pii> g[maxn*2];

ll min_distance(vector<signed> x, vector<signed> h, vector<signed> il, vector<signed> ir, vector<signed> iy, signed startx, signed endx) {
    int n = SZ(x), m = SZ(il);
    vector<pii> in, out;
    for (int i = 0; i<m; ++i) {
        in.pb({il[i], iy[i]});
        out.pb({ir[i], iy[i]});
    }
    sort(ALL(in));
    sort(ALL(out));

//    sort(ALL(bds), [&](Bd a, Bd b) { return a.y > b.y; });
    map<int, int> cut;
    vector<map<int, int> > hv(n);
    int ID = 0;
    int oj = 0, ij = 0;
    int S, T;
//    set<int> dontkill;
    map<int, int> last; // last to have this
    for (int i = 0; i<n; ++i) {
        set<int> app; // newly appeared
        while (oj < m && out[oj].f < i) {
//            if (!dontkill.count(out[oj].s)){
            --cut[out[oj].s];
            if (cut[out[oj].s] == 0) cut.erase(out[oj].s);
//                bug(i,"Ridded",out[oj].s);
//            }
            ++oj;
        }
        while (ij < m && in[ij].f <= i) {
            if (cut[in[ij].s] == 0) app.insert(in[ij].s);
            ++cut[(in[ij].s)];
            ++ij;
        }
//        bug(i, SZ(cut));
        map<int, int>::iterator it = cut.begin();
        int prvid = ID++, prvh = 0;
        if (i == startx) S = prvid;
        if (i == endx) T = prvid;
        while (it != cut.end() && (*it).f <= h[i]) {
            int H = (*it).f;
            hv[i][H] = ID;
            g[prvid].pb({ID, H - prvh});
            g[ID].pb({prvid, H - prvh});
            bug(i, H-prvh);
//            bug(i, H);
            if (i && !app.count(H)) {
                int j = last[H];
                int df = x[i]-x[j];
                g[ID].pb({hv[j][H], df});
                g[hv[j][H]].pb({ID, df});
                bug("back", i, H, df);
            }
            last[H] = i;
            prvh = H;
            prvid = ID;
            ++ID;
            ++it;
        }
    }
    bug(ID, S, T);
    vector<ll> d(ID, 0x3f3f3f3f3f3f3f3f);
    priority_queue<pli, vector<pli >, greater<pli> > pq;
    d[S] = 0;
    pq.push({0,S});
    while (!pq.empty()) {
        ll w = pq.top().f;
        int v = pq.top().s;
        pq.pop();
        if (d[v] != w) continue;
        for (pii u : g[v]) {
            if (d[u.f] > w + u.s) {
                d[u.f] = w + u.s;
                pq.push({d[u.f], u.f});
            }
        }
    }
//    for (int i = 0; i<ID; i++) {
//        for (pii u : g[i]) {
//            bug(i,u.f, u.s);
//        }
//    }
//    for (int i = 0; i<ID; i++) {
//        bug(i, d[i]);
//    }
    if (d[T] == 0x3f3f3f3f3f3f3f3f) d[T] = -1;
    return d[T];

}

#ifdef BALBIT
signed main(){
    IOS();
//    int MO = min_distance({0, 4, 5, 6, 9},
//{6, 6, 6, 6, 6},
//{3, 1, 0},
//{4, 3, 2},
//{1, 3, 6},
//0, 4);
//    bug(MO);
    int MO2 = min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4, 5},
{1, 2, 6, 3, 6, 4, 5, 6},
{1, 6, 8, 1, 7, 2, 5, 5},
1, 5);
    bug(MO2);
}
#endif

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:122:12: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (d[T] == 0x3f3f3f3f3f3f3f3f) d[T] = -1;
            ^
walk.cpp:100:8: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
     d[S] = 0;
        ^

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43