Submission #238986

#	Time	Username	Problem	Language	Result	Execution time	Memory
238986		duality	Sky Walking (IOI19_walk)	C++14	100 / 100	1218 ms	104368 KiB

walk

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

vi events[100000];
vpii events2;
multiset<int> S;
map<int,int> M;
vi vv[100000],nodes[100000];
int xx[1200002];
vpii adjList[1200002];
LLI dist[1200002];
priority_queue<pair<LLI,int> > H;
long long int min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g) {
    int i,j,n = x.size(),m = y.size(),num = 0;
    for (i = 0; i < n; i++) events2.pb(mp(h[i],i));
    for (i = 0; i < m; i++) events[l[i]].pb(i),events[r[i]].pb(i),events2.pb(mp(y[i],-i-1));
    sort(events2.begin(),events2.end(),greater<pii>());
    for (i = 0; i < events2.size(); i++) {
        if (events2[i].second >= 0) S.insert(events2[i].second);
        else {
            int v = -events2[i].second-1;
            auto it = S.lower_bound(s);
            if ((it != S.end()) && (*it > l[v]) && (*it < r[v])) events[*it].pb(v);
            if (it != S.begin()) {
                it--;
                if ((*it > l[v]) && (*it < r[v])) events[*it].pb(v);
            }
            it = S.lower_bound(g);
            if ((it != S.end()) && (*it > l[v]) && (*it < r[v])) events[*it].pb(v);
            if (it != S.begin()) {
                it--;
                if ((*it > l[v]) && (*it < r[v])) events[*it].pb(v);
            }
        }
    }
    S.clear(),vv[s].pb(0),vv[g].pb(0);
    for (i = 0; i < n; i++) {
        for (j = 0; j < events[i].size(); j++) {
            if (l[events[i][j]] == i) S.insert(y[events[i][j]]);
        }
        for (j = 0; j < events[i].size(); j++) {
            vv[i].pb(y[events[i][j]]);
            auto it = S.lower_bound(y[events[i][j]]);
            if (it != S.begin()) vv[i].pb(*(--it));
        }
        for (j = 0; j < events[i].size(); j++) {
            if (r[events[i][j]] == i) S.erase(S.find(y[events[i][j]]));
        }
        sort(vv[i].begin(),vv[i].end());
        vv[i].resize(unique(vv[i].begin(),vv[i].end())-vv[i].begin());
        for (j = 0; j < vv[i].size(); j++) nodes[i].pb(num++),xx[num-1] = x[i];
        for (j = 1; j < vv[i].size(); j++) {
            adjList[nodes[i][j-1]].pb(mp(nodes[i][j],vv[i][j]-vv[i][j-1]));
            adjList[nodes[i][j]].pb(mp(nodes[i][j-1],vv[i][j]-vv[i][j-1]));
        }
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < vv[i].size(); j++) {
            if (M.count(vv[i][j])) {
                int v = M[vv[i][j]];
                adjList[v].pb(mp(nodes[i][j],x[i]-xx[v]));
                adjList[nodes[i][j]].pb(mp(v,x[i]-xx[v]));
                M[vv[i][j]] = nodes[i][j];
            }
        }
        for (j = 0; j < events[i].size(); j++) {
            int v = events[i][j];
            if (r[v] == i) M.erase(y[v]);
        }
        for (j = 0; j < events[i].size(); j++) {
            int v = events[i][j];
            if (l[v] == i) M[y[v]] = nodes[i][lower_bound(vv[i].begin(),vv[i].end(),y[v])-vv[i].begin()];
        }
    }
    fill(dist,dist+num,-1);
    dist[nodes[s][0]] = 0,H.push(mp(0,nodes[s][0]));
    while (!H.empty()) {
        int u = H.top().second;
        LLI d = -H.top().first;
        H.pop();

        if (d > dist[u]) continue;
        else if (u == nodes[g][0]) return d;
        for (i = 0; i < adjList[u].size(); i++) {
            int v = adjList[u][i].first;
            if ((dist[v] == -1) || (dist[u]+adjList[u][i].second < dist[v])) {
                dist[v] = dist[u]+adjList[u][i].second;
                H.push(mp(-dist[v],v));
            }
        }
    }
    return -1;
}

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:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < events2.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~
walk.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
walk.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
walk.cpp:100:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
walk.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < vv[i].size(); j++) nodes[i].pb(num++),xx[num-1] = x[i];
                     ~~^~~~~~~~~~~~~~
walk.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 1; j < vv[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~
walk.cpp:112:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < vv[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~
walk.cpp:120:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
walk.cpp:124:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
walk.cpp:138:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~

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