oj.uz

Submission #719905

# Submission time Handle Problem Language Result Execution time Memory
719905 2023-04-07T04:09:06 Z joelgun14 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 36940 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++;
    }
    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);
        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 && !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].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].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 && !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].lb(idx) != s[x].end()) {
                    int tmp = *s[x].lb(idx);
                    if(weights[tmp].size()) {
                        nxtidx = tmp;
                        break;
                    }
                    s[x].erase(s[x].lb(idx));
                }
                while(s[x].lb(idx) != s[x].begin()) {
                    int tmp = *--s[x].lb(idx);
                    if(weights[tmp].size()) {
                        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 8 ms 6228 KB Output is correct
3 Correct 7 ms 6228 KB Output is correct
4 Correct 7 ms 6228 KB Output is correct
5 Correct 7 ms 6228 KB Output is correct
6 Correct 9 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 8 ms 6228 KB Output is correct
2 Correct 7 ms 6228 KB Output is correct
3 Correct 7 ms 6228 KB Output is correct
4 Correct 9 ms 6228 KB Output is correct
5 Correct 8 ms 6228 KB Output is correct
6 Correct 8 ms 6296 KB Output is correct
7 Correct 8 ms 6228 KB Output is correct
8 Correct 9 ms 6420 KB Output is correct
9 Correct 8 ms 6548 KB Output is correct
10 Correct 16 ms 7204 KB Output is correct
11 Correct 48 ms 7212 KB Output is correct
12 Correct 26 ms 6292 KB Output is correct
13 Correct 35 ms 7136 KB Output is correct
14 Correct 44 ms 6856 KB Output is correct
15 Correct 41 ms 6860 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6228 KB Output is correct
2 Correct 7 ms 6228 KB Output is correct
3 Correct 7 ms 6228 KB Output is correct
4 Correct 7 ms 6228 KB Output is correct
5 Correct 7 ms 6228 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 8 ms 6228 KB Output is correct
8 Correct 9 ms 6356 KB Output is correct
9 Correct 9 ms 6484 KB Output is correct
10 Correct 16 ms 7192 KB Output is correct
11 Correct 44 ms 7212 KB Output is correct
12 Correct 32 ms 6360 KB Output is correct
13 Correct 30 ms 7204 KB Output is correct
14 Correct 38 ms 6832 KB Output is correct
15 Correct 38 ms 6860 KB Output is correct
16 Correct 33 ms 8108 KB Output is correct
17 Execution timed out 1114 ms 35312 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6228 KB Output is correct
2 Correct 7 ms 6228 KB Output is correct
3 Correct 7 ms 6228 KB Output is correct
4 Correct 10 ms 6228 KB Output is correct
5 Correct 7 ms 6228 KB Output is correct
6 Correct 10 ms 6296 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 9 ms 6380 KB Output is correct
9 Correct 9 ms 6484 KB Output is correct
10 Correct 21 ms 7124 KB Output is correct
11 Correct 47 ms 7200 KB Output is correct
12 Correct 30 ms 6356 KB Output is correct
13 Correct 33 ms 7116 KB Output is correct
14 Correct 38 ms 6840 KB Output is correct
15 Correct 39 ms 7008 KB Output is correct
16 Correct 29 ms 8020 KB Output is correct
17 Execution timed out 1113 ms 36940 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6228 KB Output is correct
2 Correct 7 ms 6280 KB Output is correct
3 Correct 7 ms 6264 KB Output is correct
4 Correct 8 ms 6288 KB Output is correct
5 Correct 7 ms 6228 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 10 ms 6300 KB Output is correct
8 Correct 8 ms 6416 KB Output is correct
9 Correct 8 ms 6484 KB Output is correct
10 Correct 17 ms 7124 KB Output is correct
11 Correct 48 ms 7340 KB Output is correct
12 Correct 30 ms 6360 KB Output is correct
13 Correct 34 ms 7116 KB Output is correct
14 Correct 41 ms 6904 KB Output is correct
15 Correct 47 ms 6852 KB Output is correct
16 Correct 31 ms 8068 KB Output is correct
17 Execution timed out 1120 ms 36484 KB Time limit exceeded
18 Halted 0 ms 0 KB -