oj.uz

Submission #719904

# Submission time Handle Problem Language Result Execution time Memory
719904 2023-04-07T04:06:10 Z joelgun14 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 37684 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>, 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;
        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[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)
                        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;
                    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) {
                        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;
                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) {
                    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 7 ms 6228 KB Output is correct
2 Correct 7 ms 6228 KB Output is correct
3 Correct 7 ms 6284 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 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 8 ms 6228 KB Output is correct
4 Correct 9 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 9 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 17 ms 7180 KB Output is correct
11 Correct 46 ms 7204 KB Output is correct
12 Correct 28 ms 6356 KB Output is correct
13 Correct 34 ms 7228 KB Output is correct
14 Correct 43 ms 6832 KB Output is correct
15 Correct 39 ms 6876 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6228 KB Output is correct
2 Correct 9 ms 6228 KB Output is correct
3 Correct 7 ms 6176 KB Output is correct
4 Correct 8 ms 6228 KB Output is correct
5 Correct 8 ms 6296 KB Output is correct
6 Correct 7 ms 6228 KB Output is correct
7 Correct 8 ms 6228 KB Output is correct
8 Correct 8 ms 6356 KB Output is correct
9 Correct 9 ms 6484 KB Output is correct
10 Correct 17 ms 7124 KB Output is correct
11 Correct 46 ms 7124 KB Output is correct
12 Correct 29 ms 6356 KB Output is correct
13 Correct 32 ms 7232 KB Output is correct
14 Correct 40 ms 6856 KB Output is correct
15 Correct 40 ms 6884 KB Output is correct
16 Correct 29 ms 8140 KB Output is correct
17 Execution timed out 1114 ms 37684 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6228 KB Output is correct
2 Correct 10 ms 6272 KB Output is correct
3 Correct 7 ms 6228 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 9 ms 6228 KB Output is correct
8 Correct 8 ms 6340 KB Output is correct
9 Correct 10 ms 6568 KB Output is correct
10 Correct 17 ms 7124 KB Output is correct
11 Correct 45 ms 7228 KB Output is correct
12 Correct 28 ms 6356 KB Output is correct
13 Correct 32 ms 7184 KB Output is correct
14 Correct 43 ms 6852 KB Output is correct
15 Correct 44 ms 6868 KB Output is correct
16 Correct 34 ms 8104 KB Output is correct
17 Execution timed out 1109 ms 36640 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 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 8 ms 6296 KB Output is correct
6 Correct 8 ms 6212 KB Output is correct
7 Correct 7 ms 6240 KB Output is correct
8 Correct 8 ms 6356 KB Output is correct
9 Correct 9 ms 6484 KB Output is correct
10 Correct 18 ms 7124 KB Output is correct
11 Correct 46 ms 7184 KB Output is correct
12 Correct 29 ms 6356 KB Output is correct
13 Correct 33 ms 7168 KB Output is correct
14 Correct 39 ms 6860 KB Output is correct
15 Correct 41 ms 6844 KB Output is correct
16 Correct 28 ms 8076 KB Output is correct
17 Execution timed out 1120 ms 36556 KB Time limit exceeded
18 Halted 0 ms 0 KB -