Submission #282072

#TimeUsernameProblemLanguageResultExecution timeMemory
282072peti1234Sky Walking (IOI19_walk)C++17
24 / 100
2773 ms820296 KiB
#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++) {
      |                           ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...