oj.uz

Submission #719911

# Submission time Handle Problem Language Result Execution time Memory
719911 2023-04-07T04:23:37 Z joelgun14 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 68784 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define mp make_pair
#define fi first
#define lb lower_bound
#define se second
#define endl "\n"
using namespace std;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    int blk = 100;
    vector<int> weights[n];
    int init = -1, initp = -1, target = -1;
    map<pair<int, int>, int> pti;
    set<int> s[(int)1e5];
    int t = 0;
    for(int i = 1; i <= blk; ++i) {
        for(int j = 0; j < i; ++j)
            pti[mp(j, i)] = t++;
    }
    bool done[n];
    memset(done, 0, sizeof(done));
    for(int i = 1; i <= m; ++i) {
        int b, p;
        cin >> b >> p;
        if(i == 1)
            init = b, initp = p;
        else if(i == 2)
            target = b;
        // b -> pos
        // p -> multiple
        weights[b].push_back(p);
        if(!done[b]) {
            for(int j = 1; j <= blk; ++j) {
                //cout << "INSERT " << b % j << " " << j << " " << b << endl;
                s[pti[mp(b % j, j)]].insert(b);
            }
            done[b] = 1;
        }
    }
    // gaperlu cek semua cukup cek yg ada weights
    // kalo udh proc weight jg gperlu
    // kalo <= blk maka memo tiap pair int modulo dalam vector
    // kalo > blk maka cek manual
    // doge cmn boleh gerak dr ori node (gaboleh meet di tengah)
    // hence cukup dijkstra dengan 1 origin, terus klo intersect lainnya bs langsung dijkstra aja
    // tiap node ada theoretically n^2 dijkstra state yg mgkn?
    // tp yg high modulo itu sparse, jadi bs simpan manual pakai sorted vector/semacamnya
    priority_queue<pair<int, pair<int, pair<int, int>>>, vector<pair<int, pair<int, pair<int, int>>>>, greater<pair<int, pair<int, pair<int, int>>>>> pq;
    // fi -> dist
    // se.fi -> idx
    // se.se.fi -> current p
    // se.se.se -> tanda dr atas/bawah
    // guna -> reduce double counting
    //cout << init << " " << initp << endl;
    pq.push(mp(0, mp(init, mp(initp, -1))));
    int d[n + 1];
    unordered_map<int, bool, custom_hash> vis[n];
    memset(d, -1, sizeof(d));
    // cek ada yg bs sampai ke target atau tidak, kalo tidak langsung output false
    // kalo iya, maka ada pembuktian min path tidak sepanjang itu?
    while(pq.size()) {
        int dist = pq.top().fi, idx = pq.top().se.fi, curp = pq.top().se.se.fi, tanda = pq.top().se.se.se;
        pq.pop();
        //cout << dist << " " << idx << " " << curp << endl;
        if(vis[idx][curp])
            continue;
        if(d[idx] == -1)
            d[idx] = dist;
        d[idx] = min(d[idx], dist);
        for(auto i : weights[idx]) {
            if(!vis[idx][i] && i != curp) {
                if(i > blk) {
                    int tmp = idx + i;
                    while(tmp < n && !weights[tmp].size())
                        tmp += i;
                    if(tmp < n && !vis[tmp][i])
                        pq.push(mp(dist + (tmp - idx) / i, mp(tmp, mp(i, 0))));
                    tmp = idx - i;
                    while(tmp >= 0 && !weights[tmp].size())
                        tmp -= i;
                    if(tmp >= 0 && !vis[tmp][i]) 
                        pq.push(mp(dist + (idx - tmp) / i, mp(tmp, mp(i, 1))));
                }
                else {
                    int mres = idx % i;
                    int x = pti[mp(mres, i)];
                    int nxtidx = -1, pridx = -1;
                    while(s[x].size() && s[x].lb(idx) != s[x].end()) {
                        int tmp = *s[x].lb(idx);
                        //cout << "FIND NXT " << tmp << " " << weights[tmp].size() << endl;
                        if(weights[tmp].size() && tmp != idx) {
                            nxtidx = tmp;
                            break;
                        }
                        s[x].erase(s[x].lb(idx));
                    }
                    while(s[x].size() && s[x].lb(idx) != s[x].begin()) {
                        int tmp = *--s[x].lb(idx);
                        if(weights[tmp].size() && tmp != idx) {
                            pridx = tmp;
                            break;
                        }
                        s[x].erase(--s[x].lb(idx));
                    }
                    //cout << nxtidx << " " <<pridx << endl;
                    if(nxtidx != -1 && !vis[nxtidx][i]) {
                        pq.push(mp(dist + (nxtidx - idx) / i, mp(nxtidx, mp(i, 0))));
                    }
                    if(pridx != -1 && !vis[pridx][i]) {
                        pq.push(mp(dist + (idx - pridx) / i, mp(pridx, mp(i, 1))));
                    }
                }
                vis[idx][i] = 1;
            }
        }
        weights[idx].clear();
        //cout << idx << " " << curp << endl;
        if(!vis[idx][curp]) {
            vis[idx][curp] = 1;
            //cout << dist << " " << idx << " " << curp << endl;
            if(curp > blk) {
                int tmp = idx + curp;
                if(tanda != 1) {
                    while(tmp < n && !weights[tmp].size())
                        tmp += curp;
                    if(tmp < n && !vis[tmp][curp])
                        pq.push(mp(dist + (tmp - idx) / curp, mp(tmp, mp(curp, 0))));
                }
                if(tanda != 0) {
                    tmp = idx - curp;
                    while(tmp >= 0 && !weights[tmp].size())
                        tmp -= curp;
                    if(tmp >= 0 && !vis[tmp][curp]) 
                        pq.push(mp(dist + (idx - tmp) / curp, mp(tmp, mp(curp, 1))));
                }
            }
            else {
                int mres = idx % curp;
                int x = pti[mp(mres, curp)];
                int nxtidx = -1, pridx = -1;
                while(s[x].size() && s[x].lb(idx) != s[x].end()) {
                    int tmp = *s[x].lb(idx);
                    if(weights[tmp].size() && tmp != idx) {
                        nxtidx = tmp;
                        break;
                    }
                    s[x].erase(s[x].lb(idx));
                }
                while(s[x].size() && s[x].lb(idx) != s[x].begin()) {
                    int tmp = *--s[x].lb(idx);
                    if(weights[tmp].size() && tmp != idx) {
                        pridx = tmp;
                        break;
                    }
                    s[x].erase(--s[x].lb(idx));
                }
                //cout << nxtidx << " " << pridx << endl;
                if(nxtidx != -1 && tanda != 1 && !vis[nxtidx][curp]) {
                    pq.push(mp(dist + (nxtidx - idx) / curp, mp(nxtidx, mp(curp, 0))));
                }
                if(pridx != -1 && tanda != 0 && !vis[pridx][curp]) {
                    pq.push(mp(dist + (idx - pridx) / curp, mp(pridx, mp(curp, 1))));
                }
            }
        }
        if(idx == target)
            break;
    }
    cout << d[target] << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 5 ms 5260 KB Output is correct
6 Correct 6 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5336 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 4 ms 5376 KB Output is correct
10 Correct 5 ms 5744 KB Output is correct
11 Correct 7 ms 5716 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 5 ms 5716 KB Output is correct
14 Correct 6 ms 5716 KB Output is correct
15 Correct 6 ms 5716 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5332 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 5 ms 5716 KB Output is correct
11 Correct 6 ms 5716 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 6 ms 5716 KB Output is correct
14 Correct 6 ms 5716 KB Output is correct
15 Correct 6 ms 5716 KB Output is correct
16 Correct 8 ms 6228 KB Output is correct
17 Correct 23 ms 8756 KB Output is correct
18 Correct 25 ms 9052 KB Output is correct
19 Correct 19 ms 7764 KB Output is correct
20 Correct 86 ms 15112 KB Output is correct
21 Correct 13 ms 7124 KB Output is correct
22 Correct 21 ms 8328 KB Output is correct
23 Correct 27 ms 8908 KB Output is correct
24 Correct 44 ms 11288 KB Output is correct
25 Correct 52 ms 11508 KB Output is correct
26 Correct 6 ms 5844 KB Output is correct
27 Correct 5 ms 5716 KB Output is correct
28 Correct 90 ms 15160 KB Output is correct
29 Correct 4 ms 5716 KB Output is correct
30 Correct 4 ms 5588 KB Output is correct
31 Correct 5 ms 5652 KB Output is correct
32 Correct 6 ms 5716 KB Output is correct
33 Correct 7 ms 5844 KB Output is correct
34 Correct 7 ms 5812 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 6 ms 5716 KB Output is correct
11 Correct 7 ms 5716 KB Output is correct
12 Correct 4 ms 5304 KB Output is correct
13 Correct 5 ms 5716 KB Output is correct
14 Correct 8 ms 5716 KB Output is correct
15 Correct 6 ms 5716 KB Output is correct
16 Correct 9 ms 6276 KB Output is correct
17 Correct 24 ms 8772 KB Output is correct
18 Correct 25 ms 8968 KB Output is correct
19 Correct 16 ms 7764 KB Output is correct
20 Correct 81 ms 15180 KB Output is correct
21 Correct 12 ms 7120 KB Output is correct
22 Correct 19 ms 8212 KB Output is correct
23 Correct 33 ms 8888 KB Output is correct
24 Correct 39 ms 11212 KB Output is correct
25 Correct 47 ms 11416 KB Output is correct
26 Correct 6 ms 5844 KB Output is correct
27 Correct 5 ms 5728 KB Output is correct
28 Correct 78 ms 15228 KB Output is correct
29 Correct 5 ms 5716 KB Output is correct
30 Correct 4 ms 5588 KB Output is correct
31 Correct 5 ms 5716 KB Output is correct
32 Correct 5 ms 5716 KB Output is correct
33 Correct 6 ms 5916 KB Output is correct
34 Correct 7 ms 5844 KB Output is correct
35 Correct 78 ms 13808 KB Output is correct
36 Correct 45 ms 10572 KB Output is correct
37 Correct 116 ms 15936 KB Output is correct
38 Correct 96 ms 15824 KB Output is correct
39 Correct 88 ms 15056 KB Output is correct
40 Correct 81 ms 15104 KB Output is correct
41 Correct 101 ms 15556 KB Output is correct
42 Correct 11 ms 6088 KB Output is correct
43 Correct 9 ms 5972 KB Output is correct
44 Correct 91 ms 15280 KB Output is correct
45 Correct 29 ms 8700 KB Output is correct
46 Correct 28 ms 8712 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5332 KB Output is correct
2 Correct 5 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 5 ms 5332 KB Output is correct
9 Correct 5 ms 5464 KB Output is correct
10 Correct 7 ms 5812 KB Output is correct
11 Correct 5 ms 5716 KB Output is correct
12 Correct 4 ms 5312 KB Output is correct
13 Correct 6 ms 5716 KB Output is correct
14 Correct 6 ms 5716 KB Output is correct
15 Correct 6 ms 5716 KB Output is correct
16 Correct 11 ms 6228 KB Output is correct
17 Correct 26 ms 8740 KB Output is correct
18 Correct 26 ms 8964 KB Output is correct
19 Correct 19 ms 7744 KB Output is correct
20 Correct 102 ms 15092 KB Output is correct
21 Correct 14 ms 6996 KB Output is correct
22 Correct 24 ms 8196 KB Output is correct
23 Correct 28 ms 8988 KB Output is correct
24 Correct 39 ms 11272 KB Output is correct
25 Correct 43 ms 11468 KB Output is correct
26 Correct 6 ms 5844 KB Output is correct
27 Correct 6 ms 5716 KB Output is correct
28 Correct 98 ms 15264 KB Output is correct
29 Correct 5 ms 5716 KB Output is correct
30 Correct 6 ms 5616 KB Output is correct
31 Correct 5 ms 5716 KB Output is correct
32 Correct 5 ms 5748 KB Output is correct
33 Correct 6 ms 5844 KB Output is correct
34 Correct 6 ms 5844 KB Output is correct
35 Correct 73 ms 13800 KB Output is correct
36 Correct 42 ms 10632 KB Output is correct
37 Correct 87 ms 15948 KB Output is correct
38 Correct 93 ms 15852 KB Output is correct
39 Correct 87 ms 15056 KB Output is correct
40 Correct 105 ms 15136 KB Output is correct
41 Correct 100 ms 15512 KB Output is correct
42 Correct 10 ms 6080 KB Output is correct
43 Correct 11 ms 5972 KB Output is correct
44 Correct 90 ms 15308 KB Output is correct
45 Correct 27 ms 8628 KB Output is correct
46 Correct 30 ms 8692 KB Output is correct
47 Correct 930 ms 59112 KB Output is correct
48 Execution timed out 1075 ms 68784 KB Time limit exceeded
49 Halted 0 ms 0 KB -