oj.uz

Submission #719901

# Submission time Handle Problem Language Result Execution time Memory
719901 2023-04-07T03:50:31 Z joelgun14 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 33328 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;
    bool ansexist = 0;
    map<pair<int, int>, set<int>> s;
    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;
        if(i != 2) {
            if(b % p == init % p)
                ansexist = 1;
        }
        // b -> pos
        // p -> multiple
        weights[b].push_back(p);
        for(int j = 1; j <= blk; ++j) {
            //cout << "INSERT " << b % j << " " << j << " " << b << endl;
            s[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)
                        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) 
                        pq.push(mp(dist + (idx - tmp) / i, mp(tmp, mp(i, 1))));
                }
                else {
                    int mres = idx % i;
                    auto &x = s[mp(mres, i)];
                    int nxtidx = -1, pridx = -1;
                    while(x.lb(idx) != x.end()) {
                        int tmp = *x.lb(idx);
                        //cout << "FIND NXT " << tmp << " " << weights[tmp].size() << endl;
                        if(weights[tmp].size() && tmp != idx) {
                            nxtidx = tmp;
                            break;
                        }
                        x.erase(x.lb(idx));
                    }
                    while(x.lb(idx) != x.begin()) {
                        int tmp = *--x.lb(idx);
                        if(weights[tmp].size() && tmp != idx) {
                            pridx = tmp;
                            break;
                        }
                        x.erase(--x.lb(idx));
                    }
                    //cout << nxtidx << " " <<pridx << endl;
                    if(nxtidx != -1) {
                        pq.push(mp(dist + (nxtidx - idx) / i, mp(nxtidx, mp(i, 0))));
                    }
                    if(pridx != -1) {
                        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)
                        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) 
                        pq.push(mp(dist + (idx - tmp) / curp, mp(tmp, mp(curp, 1))));
                }
            }
            else {
                int mres = idx % curp;
                auto &x = s[mp(mres, curp)];
                int nxtidx = -1, pridx = -1;
                while(x.lb(idx) != x.end()) {
                    int tmp = *x.lb(idx);
                    if(weights[tmp].size()) {
                        nxtidx = tmp;
                        break;
                    }
                    x.erase(x.lb(idx));
                }
                while(x.lb(idx) != x.begin()) {
                    int tmp = *--x.lb(idx);
                    if(weights[tmp].size()) {
                        pridx = tmp;
                        break;
                    }
                    x.erase(--x.lb(idx));
                }
                //cout << nxtidx << " " << pridx << endl;
                if(nxtidx != -1 && tanda != 1) {
                    pq.push(mp(dist + (nxtidx - idx) / curp, mp(nxtidx, mp(curp, 0))));
                }
                if(pridx != -1 && tanda != 0) {
                    pq.push(mp(dist + (idx - pridx) / curp, mp(pridx, mp(curp, 1))));
                }
            }
        }
        if(idx == target)
            break;
    }
    cout << d[target] << endl;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:30:10: warning: variable 'ansexist' set but not used [-Wunused-but-set-variable]
   30 |     bool ansexist = 0;
      |          ^~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 14 ms 2568 KB Output is correct
11 Correct 38 ms 2644 KB Output is correct
12 Correct 15 ms 536 KB Output is correct
13 Correct 24 ms 2620 KB Output is correct
14 Correct 31 ms 2000 KB Output is correct
15 Correct 31 ms 1912 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 11 ms 2568 KB Output is correct
11 Correct 47 ms 2644 KB Output is correct
12 Correct 16 ms 552 KB Output is correct
13 Correct 27 ms 2644 KB Output is correct
14 Correct 33 ms 1916 KB Output is correct
15 Correct 34 ms 1948 KB Output is correct
16 Correct 26 ms 4040 KB Output is correct
17 Execution timed out 1116 ms 33328 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 12 ms 2664 KB Output is correct
11 Correct 40 ms 2660 KB Output is correct
12 Correct 14 ms 468 KB Output is correct
13 Correct 25 ms 2644 KB Output is correct
14 Correct 31 ms 1996 KB Output is correct
15 Correct 31 ms 1944 KB Output is correct
16 Correct 24 ms 4032 KB Output is correct
17 Execution timed out 1121 ms 33040 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 10 ms 2588 KB Output is correct
11 Correct 38 ms 2664 KB Output is correct
12 Correct 16 ms 596 KB Output is correct
13 Correct 25 ms 2624 KB Output is correct
14 Correct 34 ms 1996 KB Output is correct
15 Correct 34 ms 1904 KB Output is correct
16 Correct 25 ms 4052 KB Output is correct
17 Execution timed out 1116 ms 33036 KB Time limit exceeded
18 Halted 0 ms 0 KB -