oj.uz

Submission #719909

# Submission time Handle Problem Language Result Execution time Memory
719909 2023-04-07T04:16:10 Z joelgun14 Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 1000 ms 25584 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);
            }
        }
    }
    // 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 << 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]) {
                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 << curp << " " << blk << 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 7 ms 6228 KB Output is correct
2 Correct 6 ms 6228 KB Output is correct
3 Correct 9 ms 6240 KB Output is correct
4 Correct 8 ms 6228 KB Output is correct
5 Correct 7 ms 6292 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6228 KB Output is correct
2 Correct 8 ms 6228 KB Output is correct
3 Correct 10 ms 6228 KB Output is correct
4 Correct 8 ms 6228 KB Output is correct
5 Correct 8 ms 6228 KB Output is correct
6 Correct 7 ms 6228 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 10 ms 6356 KB Output is correct
9 Correct 9 ms 6504 KB Output is correct
10 Correct 16 ms 7232 KB Output is correct
11 Correct 44 ms 7224 KB Output is correct
12 Correct 26 ms 6352 KB Output is correct
13 Correct 31 ms 7176 KB Output is correct
14 Correct 39 ms 6852 KB Output is correct
15 Correct 45 ms 6856 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6228 KB Output is correct
2 Correct 9 ms 6228 KB Output is correct
3 Correct 10 ms 6228 KB Output is correct
4 Correct 8 ms 6228 KB Output is correct
5 Correct 8 ms 6228 KB Output is correct
6 Correct 7 ms 6228 KB Output is correct
7 Correct 9 ms 6228 KB Output is correct
8 Correct 8 ms 6356 KB Output is correct
9 Correct 7 ms 6484 KB Output is correct
10 Correct 16 ms 7116 KB Output is correct
11 Correct 47 ms 7204 KB Output is correct
12 Correct 31 ms 6356 KB Output is correct
13 Correct 33 ms 7120 KB Output is correct
14 Correct 42 ms 6852 KB Output is correct
15 Correct 38 ms 6916 KB Output is correct
16 Correct 30 ms 8088 KB Output is correct
17 Correct 118 ms 12884 KB Output is correct
18 Correct 70 ms 13580 KB Output is correct
19 Correct 45 ms 10892 KB Output is correct
20 Correct 233 ms 25460 KB Output is correct
21 Correct 48 ms 9736 KB Output is correct
22 Correct 52 ms 11804 KB Output is correct
23 Correct 73 ms 13296 KB Output is correct
24 Correct 169 ms 17864 KB Output is correct
25 Correct 214 ms 18368 KB Output is correct
26 Correct 48 ms 7212 KB Output is correct
27 Correct 42 ms 6928 KB Output is correct
28 Correct 243 ms 25584 KB Output is correct
29 Correct 19 ms 6744 KB Output is correct
30 Correct 11 ms 6640 KB Output is correct
31 Correct 17 ms 6872 KB Output is correct
32 Correct 14 ms 6868 KB Output is correct
33 Correct 38 ms 7040 KB Output is correct
34 Correct 43 ms 7108 KB Output is correct

Subtask #4
0 / 21.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 6228 KB Output is correct
4 Correct 8 ms 6228 KB Output is correct
5 Correct 7 ms 6224 KB Output is correct
6 Correct 9 ms 6228 KB Output is correct
7 Correct 8 ms 6276 KB Output is correct
8 Correct 9 ms 6356 KB Output is correct
9 Correct 8 ms 6484 KB Output is correct
10 Correct 17 ms 7204 KB Output is correct
11 Correct 49 ms 7124 KB Output is correct
12 Correct 28 ms 6356 KB Output is correct
13 Correct 31 ms 7112 KB Output is correct
14 Correct 39 ms 6944 KB Output is correct
15 Correct 42 ms 6876 KB Output is correct
16 Correct 29 ms 8012 KB Output is correct
17 Correct 116 ms 12856 KB Output is correct
18 Correct 97 ms 13488 KB Output is correct
19 Correct 52 ms 10872 KB Output is correct
20 Correct 241 ms 25576 KB Output is correct
21 Correct 47 ms 9804 KB Output is correct
22 Correct 52 ms 11912 KB Output is correct
23 Correct 72 ms 13388 KB Output is correct
24 Correct 163 ms 17776 KB Output is correct
25 Correct 207 ms 18292 KB Output is correct
26 Correct 43 ms 7076 KB Output is correct
27 Correct 41 ms 6932 KB Output is correct
28 Correct 237 ms 25512 KB Output is correct
29 Correct 19 ms 6848 KB Output is correct
30 Correct 11 ms 6668 KB Output is correct
31 Correct 17 ms 6852 KB Output is correct
32 Correct 21 ms 6868 KB Output is correct
33 Correct 40 ms 7036 KB Output is correct
34 Correct 39 ms 7016 KB Output is correct
35 Execution timed out 1101 ms 19880 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6228 KB Output is correct
2 Correct 10 ms 6228 KB Output is correct
3 Correct 9 ms 6228 KB Output is correct
4 Correct 7 ms 6228 KB Output is correct
5 Correct 9 ms 6276 KB Output is correct
6 Correct 9 ms 6288 KB Output is correct
7 Correct 8 ms 6228 KB Output is correct
8 Correct 8 ms 6356 KB Output is correct
9 Correct 12 ms 6544 KB Output is correct
10 Correct 16 ms 7124 KB Output is correct
11 Correct 44 ms 7220 KB Output is correct
12 Correct 28 ms 6368 KB Output is correct
13 Correct 31 ms 7192 KB Output is correct
14 Correct 37 ms 6848 KB Output is correct
15 Correct 38 ms 6864 KB Output is correct
16 Correct 29 ms 8096 KB Output is correct
17 Correct 142 ms 13004 KB Output is correct
18 Correct 95 ms 13492 KB Output is correct
19 Correct 41 ms 10868 KB Output is correct
20 Correct 218 ms 25420 KB Output is correct
21 Correct 49 ms 9800 KB Output is correct
22 Correct 49 ms 11872 KB Output is correct
23 Correct 72 ms 13392 KB Output is correct
24 Correct 184 ms 17732 KB Output is correct
25 Correct 159 ms 18364 KB Output is correct
26 Correct 46 ms 7032 KB Output is correct
27 Correct 47 ms 6936 KB Output is correct
28 Correct 240 ms 25548 KB Output is correct
29 Correct 19 ms 6776 KB Output is correct
30 Correct 10 ms 6612 KB Output is correct
31 Correct 22 ms 6856 KB Output is correct
32 Correct 16 ms 6868 KB Output is correct
33 Correct 37 ms 7012 KB Output is correct
34 Correct 37 ms 7032 KB Output is correct
35 Execution timed out 1079 ms 19960 KB Time limit exceeded
36 Halted 0 ms 0 KB -