Submission #282072

#	Time	Username	Problem	Language	Result	Execution time	Memory
282072		peti1234	Sky Walking (IOI19_walk)	C++17	24 / 100	2773 ms	820296 KiB

walk

#include <bits/stdc++.h>

using namespace std;
#define vi vector<int>
const int c=2000002;
int cnt=0;
map<pair<int, int>, int> mp;
set<pair<int, int> > akt;
vi sz[c], s[c], vsz[c];
bool v[c];
vector<pair<int, pair<int, int> > > p;
priority_queue<pair<long long, int> > q;
long long dist[c];
void add(int a, int b) {
    pair<int, int> c={a, b};
    if (!mp[c]) cnt++, mp[c]=cnt;
}
void pb(int x1, int y1, int x2, int y2, int d) {
    pair<int, int> s1={x1, y1}, s2={x2, y2};
    int p1=mp[s1], p2=mp[s2];
    //cout << "el " << p1 << " " << p2 << " " << d << endl;
    sz[p1].push_back(p2), sz[p2].push_back(p1);
    s[p1].push_back(d), s[p2].push_back(d);
}
long long min_distance(vi pos, vi h, vi l, vi r, vi ma, int st, int fi) {
    int n=pos.size(), m=r.size();
    for (int i=0; i<n; i++) p.push_back({pos[i], {0, i}});
    for (int i=0; i<m; i++) {
        p.push_back({pos[l[i]], {-1, i}});
        p.push_back({pos[r[i]], {1, i}});
    }
    sort(p.begin(), p.end());
    for (int i=0; i<p.size(); i++) {
        int e=p[i].second.first, id=p[i].second.second;
        //cout << e << " " << id << endl;
        if (e==-1) akt.insert({ma[id], id});
        if (e==1) akt.erase({ma[id], id});
        if (e==0) {
            int el=-1, mag=0;
            add(id, el);
            for (auto it=akt.begin(); it!=akt.end(); it++) {
                pair<int, int> q=*it;
                int fi=q.first, se=q.second;
                if (fi<=h[id]) {
                    add(id, se);
                    pb(id, el, id, se, fi-mag);
                    el=se, mag=fi;
                    vsz[se].push_back(id);
                } else break;
            }
        }
    }
    for (int i=0; i<m; i++) {
        for (int j=1; j<vsz[i].size(); j++) {
            int a=vsz[i][j-1], b=vsz[i][j], d=pos[b]-pos[a];
            pb(a, i, b, i, d);
        }
    }
    q.push({0, mp[{st, -1}]});
    while(q.size()>0) {
        long long tav=q.top().first;
        int id=q.top().second;
        q.pop();
        if (!v[id]) {
            v[id]=true, dist[id]=-tav;
            for (int i=0; i<sz[id].size(); i++) {
                int x=sz[id][i], y=s[id][i];
                if (!v[x]) {
                    q.push({tav-y, x});
                }
            }
        }
    }
    int cel=mp[{fi, -1}];
    if (!v[cel]) return -1;
    else return dist[cel];
}






/*
int b1, b2, b3, b4;
vi v1, v2, v3, v4, v5;
int main()
{
    cin >> b1 >> b2;
    for (int i=0; i<b1; i++) {
        int x; cin >> x;
        v1.push_back(x);
    }
    for (int i=0; i<b1; i++) {
        int x; cin >> x;
        v2.push_back(x);
    }
    for (int i=0; i<b2; i++) {
        int x; cin >> x;
        v3.push_back(x);
    }
    for (int i=0; i<b2; i++) {
        int x; cin >> x;
        v4.push_back(x);
    }
    for (int i=0; i<b2; i++) {
        int x; cin >> x;
        v5.push_back(x);
    }
    cin >> b3 >> b4;
    cout << min_distance(v1, v2, v3, v4, v5, b3, b4);
    return 0;
}
*/
/*
5 3
0 4 5 6 9
6 6 6 6 6
3 1 0
4 3 2
1 3 6
0 4
*/
/*
7 7
0 3 5 7 10 12 14
8 7 9 7 6 6 9
0 0 0 2 2 3 4
1 2 6 3 6 4 6
1 6 8 1 7 2 5
1 5

*/

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:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i=0; i<p.size(); i++) {
      |                   ~^~~~~~~~~
walk.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int j=1; j<vsz[i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~
walk.cpp:66:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for (int i=0; i<sz[id].size(); i++) {
      |                           ~^~~~~~~~~~~~~~

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