oj.uz

Submission #719912

# Submission time Handle Problem Language Result Execution time Memory
719912 2023-04-07T04:25:44 Z joelgun14 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 67832 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 = 200;
    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 8 ms 6228 KB Output is correct
2 Correct 7 ms 6268 KB Output is correct
3 Correct 6 ms 6292 KB Output is correct
4 Correct 7 ms 6228 KB Output is correct
5 Correct 7 ms 6228 KB Output is correct
6 Correct 7 ms 6228 KB Output is correct
7 Correct 8 ms 6228 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6228 KB Output is correct
2 Correct 10 ms 6228 KB Output is correct
3 Correct 10 ms 6288 KB Output is correct
4 Correct 8 ms 6176 KB Output is correct
5 Correct 10 ms 6208 KB Output is correct
6 Correct 7 ms 6208 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 7 ms 6304 KB Output is correct
9 Correct 8 ms 6484 KB Output is correct
10 Correct 11 ms 7140 KB Output is correct
11 Correct 12 ms 7252 KB Output is correct
12 Correct 8 ms 6356 KB Output is correct
13 Correct 11 ms 7220 KB Output is correct
14 Correct 11 ms 6868 KB Output is correct
15 Correct 11 ms 6972 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6272 KB Output is correct
2 Correct 8 ms 6176 KB Output is correct
3 Correct 9 ms 6228 KB Output is correct
4 Correct 12 ms 6200 KB Output is correct
5 Correct 10 ms 6212 KB Output is correct
6 Correct 7 ms 6228 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 9 ms 6348 KB Output is correct
9 Correct 8 ms 6568 KB Output is correct
10 Correct 10 ms 7124 KB Output is correct
11 Correct 11 ms 7156 KB Output is correct
12 Correct 8 ms 6356 KB Output is correct
13 Correct 12 ms 7252 KB Output is correct
14 Correct 10 ms 6868 KB Output is correct
15 Correct 11 ms 6868 KB Output is correct
16 Correct 15 ms 8020 KB Output is correct
17 Correct 55 ms 12928 KB Output is correct
18 Correct 79 ms 13568 KB Output is correct
19 Correct 42 ms 10956 KB Output is correct
20 Correct 228 ms 25412 KB Output is correct
21 Correct 27 ms 9780 KB Output is correct
22 Correct 63 ms 11856 KB Output is correct
23 Correct 74 ms 13340 KB Output is correct
24 Correct 113 ms 17752 KB Output is correct
25 Correct 115 ms 18324 KB Output is correct
26 Correct 11 ms 7124 KB Output is correct
27 Correct 12 ms 6892 KB Output is correct
28 Correct 230 ms 25516 KB Output is correct
29 Correct 11 ms 6868 KB Output is correct
30 Correct 9 ms 6700 KB Output is correct
31 Correct 12 ms 6784 KB Output is correct
32 Correct 10 ms 6868 KB Output is correct
33 Correct 10 ms 7072 KB Output is correct
34 Correct 12 ms 7120 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6172 KB Output is correct
2 Correct 7 ms 6228 KB Output is correct
3 Correct 8 ms 6228 KB Output is correct
4 Correct 7 ms 6228 KB Output is correct
5 Correct 10 ms 6228 KB Output is correct
6 Correct 11 ms 6228 KB Output is correct
7 Correct 10 ms 6228 KB Output is correct
8 Correct 8 ms 6356 KB Output is correct
9 Correct 10 ms 6484 KB Output is correct
10 Correct 13 ms 7124 KB Output is correct
11 Correct 13 ms 7232 KB Output is correct
12 Correct 9 ms 6368 KB Output is correct
13 Correct 13 ms 7148 KB Output is correct
14 Correct 12 ms 6972 KB Output is correct
15 Correct 12 ms 6932 KB Output is correct
16 Correct 18 ms 8032 KB Output is correct
17 Correct 67 ms 12852 KB Output is correct
18 Correct 73 ms 13536 KB Output is correct
19 Correct 44 ms 10940 KB Output is correct
20 Correct 244 ms 25496 KB Output is correct
21 Correct 28 ms 9692 KB Output is correct
22 Correct 44 ms 11784 KB Output is correct
23 Correct 70 ms 13316 KB Output is correct
24 Correct 126 ms 17812 KB Output is correct
25 Correct 128 ms 18400 KB Output is correct
26 Correct 13 ms 7124 KB Output is correct
27 Correct 10 ms 6912 KB Output is correct
28 Correct 241 ms 25536 KB Output is correct
29 Correct 8 ms 6740 KB Output is correct
30 Correct 7 ms 6612 KB Output is correct
31 Correct 11 ms 6868 KB Output is correct
32 Correct 10 ms 6888 KB Output is correct
33 Correct 12 ms 7124 KB Output is correct
34 Correct 13 ms 7132 KB Output is correct
35 Correct 205 ms 21380 KB Output is correct
36 Correct 96 ms 16624 KB Output is correct
37 Correct 221 ms 25868 KB Output is correct
38 Correct 284 ms 26212 KB Output is correct
39 Correct 252 ms 25584 KB Output is correct
40 Correct 269 ms 25440 KB Output is correct
41 Correct 256 ms 25884 KB Output is correct
42 Correct 15 ms 7380 KB Output is correct
43 Correct 17 ms 7124 KB Output is correct
44 Correct 237 ms 25524 KB Output is correct
45 Correct 42 ms 10348 KB Output is correct
46 Correct 47 ms 10172 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6228 KB Output is correct
2 Correct 7 ms 6228 KB Output is correct
3 Correct 8 ms 6256 KB Output is correct
4 Correct 7 ms 6228 KB Output is correct
5 Correct 9 ms 6228 KB Output is correct
6 Correct 8 ms 6296 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 9 ms 6424 KB Output is correct
9 Correct 8 ms 6484 KB Output is correct
10 Correct 10 ms 7204 KB Output is correct
11 Correct 11 ms 7148 KB Output is correct
12 Correct 8 ms 6356 KB Output is correct
13 Correct 12 ms 7188 KB Output is correct
14 Correct 10 ms 6864 KB Output is correct
15 Correct 10 ms 6868 KB Output is correct
16 Correct 14 ms 8020 KB Output is correct
17 Correct 57 ms 12924 KB Output is correct
18 Correct 86 ms 13524 KB Output is correct
19 Correct 71 ms 10860 KB Output is correct
20 Correct 269 ms 25524 KB Output is correct
21 Correct 26 ms 9712 KB Output is correct
22 Correct 43 ms 11820 KB Output is correct
23 Correct 76 ms 13360 KB Output is correct
24 Correct 152 ms 17812 KB Output is correct
25 Correct 159 ms 18420 KB Output is correct
26 Correct 12 ms 7132 KB Output is correct
27 Correct 11 ms 6868 KB Output is correct
28 Correct 274 ms 25604 KB Output is correct
29 Correct 10 ms 6740 KB Output is correct
30 Correct 10 ms 6584 KB Output is correct
31 Correct 13 ms 6880 KB Output is correct
32 Correct 9 ms 6868 KB Output is correct
33 Correct 14 ms 6996 KB Output is correct
34 Correct 15 ms 7124 KB Output is correct
35 Correct 158 ms 21408 KB Output is correct
36 Correct 118 ms 16532 KB Output is correct
37 Correct 263 ms 25884 KB Output is correct
38 Correct 302 ms 26164 KB Output is correct
39 Correct 256 ms 25392 KB Output is correct
40 Correct 290 ms 25416 KB Output is correct
41 Correct 307 ms 25872 KB Output is correct
42 Correct 17 ms 7380 KB Output is correct
43 Correct 15 ms 7128 KB Output is correct
44 Correct 292 ms 25592 KB Output is correct
45 Correct 44 ms 10184 KB Output is correct
46 Correct 44 ms 10124 KB Output is correct
47 Execution timed out 1092 ms 67832 KB Time limit exceeded
48 Halted 0 ms 0 KB -