oj.uz

Submission #209460

# Submission time Handle Problem Language Result Execution time Memory
209460 2020-03-14T09:44:31 Z balbit Sky Walking (IOI19_walk) C++14
24 / 100
 2236 ms 683700 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47224 KB Output is correct
2 Correct 33 ms 47224 KB Output is correct
3 Correct 34 ms 47352 KB Output is correct
4 Correct 34 ms 47352 KB Output is correct
5 Correct 34 ms 47324 KB Output is correct
6 Correct 36 ms 47316 KB Output is correct
7 Correct 34 ms 47352 KB Output is correct
8 Correct 34 ms 47352 KB Output is correct
9 Correct 34 ms 47352 KB Output is correct
10 Correct 36 ms 47352 KB Output is correct
11 Correct 34 ms 47352 KB Output is correct
12 Correct 33 ms 47224 KB Output is correct
13 Correct 33 ms 47352 KB Output is correct
14 Correct 34 ms 47352 KB Output is correct
15 Correct 34 ms 47224 KB Output is correct
16 Correct 33 ms 47352 KB Output is correct
17 Correct 34 ms 47352 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47224 KB Output is correct
2 Correct 33 ms 47224 KB Output is correct
3 Correct 1063 ms 166232 KB Output is correct
4 Correct 925 ms 176088 KB Output is correct
5 Correct 621 ms 157916 KB Output is correct
6 Correct 584 ms 146392 KB Output is correct
7 Correct 644 ms 158172 KB Output is correct
8 Correct 1326 ms 196056 KB Output is correct
9 Correct 746 ms 159064 KB Output is correct
10 Correct 1255 ms 221276 KB Output is correct
11 Correct 590 ms 117208 KB Output is correct
12 Correct 373 ms 99804 KB Output is correct
13 Correct 1056 ms 200920 KB Output is correct
14 Correct 329 ms 96988 KB Output is correct
15 Correct 275 ms 94428 KB Output is correct
16 Correct 258 ms 94172 KB Output is correct
17 Correct 252 ms 91868 KB Output is correct
18 Correct 380 ms 117084 KB Output is correct
19 Correct 44 ms 49784 KB Output is correct
20 Correct 163 ms 72548 KB Output is correct
21 Correct 220 ms 90584 KB Output is correct
22 Correct 221 ms 92760 KB Output is correct
23 Correct 388 ms 110812 KB Output is correct
24 Correct 242 ms 93272 KB Output is correct
25 Correct 233 ms 91356 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 60516 KB Output is correct
2 Runtime error 2236 ms 683700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 60516 KB Output is correct
2 Runtime error 2236 ms 683700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47224 KB Output is correct
2 Correct 33 ms 47224 KB Output is correct
3 Correct 34 ms 47352 KB Output is correct
4 Correct 34 ms 47352 KB Output is correct
5 Correct 34 ms 47324 KB Output is correct
6 Correct 36 ms 47316 KB Output is correct
7 Correct 34 ms 47352 KB Output is correct
8 Correct 34 ms 47352 KB Output is correct
9 Correct 34 ms 47352 KB Output is correct
10 Correct 36 ms 47352 KB Output is correct
11 Correct 34 ms 47352 KB Output is correct
12 Correct 33 ms 47224 KB Output is correct
13 Correct 33 ms 47352 KB Output is correct
14 Correct 34 ms 47352 KB Output is correct
15 Correct 34 ms 47224 KB Output is correct
16 Correct 33 ms 47352 KB Output is correct
17 Correct 34 ms 47352 KB Output is correct
18 Correct 33 ms 47224 KB Output is correct
19 Correct 33 ms 47224 KB Output is correct
20 Correct 1063 ms 166232 KB Output is correct
21 Correct 925 ms 176088 KB Output is correct
22 Correct 621 ms 157916 KB Output is correct
23 Correct 584 ms 146392 KB Output is correct
24 Correct 644 ms 158172 KB Output is correct
25 Correct 1326 ms 196056 KB Output is correct
26 Correct 746 ms 159064 KB Output is correct
27 Correct 1255 ms 221276 KB Output is correct
28 Correct 590 ms 117208 KB Output is correct
29 Correct 373 ms 99804 KB Output is correct
30 Correct 1056 ms 200920 KB Output is correct
31 Correct 329 ms 96988 KB Output is correct
32 Correct 275 ms 94428 KB Output is correct
33 Correct 258 ms 94172 KB Output is correct
34 Correct 252 ms 91868 KB Output is correct
35 Correct 380 ms 117084 KB Output is correct
36 Correct 44 ms 49784 KB Output is correct
37 Correct 163 ms 72548 KB Output is correct
38 Correct 220 ms 90584 KB Output is correct
39 Correct 221 ms 92760 KB Output is correct
40 Correct 388 ms 110812 KB Output is correct
41 Correct 242 ms 93272 KB Output is correct
42 Correct 233 ms 91356 KB Output is correct
43 Correct 96 ms 60516 KB Output is correct
44 Runtime error 2236 ms 683700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Halted 0 ms 0 KB -