oj.uz

Submission #719902

# Submission time Handle Problem Language Result Execution time Memory
719902 2023-04-07T04:01:50 Z joelgun14 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 37824 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;
                    auto &x = s[pti[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[pti[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 7 ms 6228 KB Output is correct
2 Correct 7 ms 6184 KB Output is correct
3 Correct 7 ms 6228 KB Output is correct
4 Correct 6 ms 6292 KB Output is correct
5 Correct 8 ms 6228 KB Output is correct
6 Correct 8 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 7 ms 6228 KB Output is correct
2 Correct 6 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 7 ms 6228 KB Output is correct
6 Correct 7 ms 6228 KB Output is correct
7 Correct 7 ms 6296 KB Output is correct
8 Correct 8 ms 6424 KB Output is correct
9 Correct 8 ms 6572 KB Output is correct
10 Correct 17 ms 7228 KB Output is correct
11 Correct 43 ms 7204 KB Output is correct
12 Correct 26 ms 6356 KB Output is correct
13 Correct 31 ms 7236 KB Output is correct
14 Correct 38 ms 6852 KB Output is correct
15 Correct 41 ms 6864 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6248 KB Output is correct
2 Correct 7 ms 6228 KB Output is correct
3 Correct 6 ms 6228 KB Output is correct
4 Correct 6 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 6 ms 6228 KB Output is correct
8 Correct 8 ms 6420 KB Output is correct
9 Correct 9 ms 6484 KB Output is correct
10 Correct 15 ms 7120 KB Output is correct
11 Correct 43 ms 7216 KB Output is correct
12 Correct 27 ms 6356 KB Output is correct
13 Correct 31 ms 7212 KB Output is correct
14 Correct 38 ms 6836 KB Output is correct
15 Correct 40 ms 6876 KB Output is correct
16 Correct 29 ms 8120 KB Output is correct
17 Execution timed out 1126 ms 37824 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 6296 KB Output is correct
2 Correct 8 ms 6276 KB Output is correct
3 Correct 9 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 7 ms 6228 KB Output is correct
8 Correct 8 ms 6460 KB Output is correct
9 Correct 8 ms 6512 KB Output is correct
10 Correct 16 ms 7124 KB Output is correct
11 Correct 44 ms 7196 KB Output is correct
12 Correct 29 ms 6360 KB Output is correct
13 Correct 33 ms 7156 KB Output is correct
14 Correct 41 ms 6840 KB Output is correct
15 Correct 42 ms 6868 KB Output is correct
16 Correct 31 ms 8136 KB Output is correct
17 Execution timed out 1106 ms 37216 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 8 ms 6228 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 6228 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 7 ms 6228 KB Output is correct
8 Correct 8 ms 6356 KB Output is correct
9 Correct 8 ms 6484 KB Output is correct
10 Correct 16 ms 7176 KB Output is correct
11 Correct 46 ms 7216 KB Output is correct
12 Correct 28 ms 6356 KB Output is correct
13 Correct 32 ms 7216 KB Output is correct
14 Correct 38 ms 6836 KB Output is correct
15 Correct 38 ms 6856 KB Output is correct
16 Correct 29 ms 8020 KB Output is correct
17 Execution timed out 1119 ms 37596 KB Time limit exceeded
18 Halted 0 ms 0 KB -