oj.uz

Submission #1016433

# Submission time Handle Problem Language Result Execution time Memory
1016433 2024-07-08T05:10:46 Z Whisper Toll (BOI17_toll) C++17
10 / 100
 178 ms 88404 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = (n) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX_NODE            50005
#define MAX_EDGE            500005


int numNode, numEdge, numQuery, k;
struct Matrix{
    int N, M;
    vector<vector<int>> F;
    Matrix(): N(0), M(0){}
    void init(int _N, int _M){
        this -> N = _N, this -> M = _M;
        F.resize(N, vector<int>(M, INF));
    }

    friend Matrix operator * (const Matrix &a, const Matrix &b){
        Matrix res; res.init(a.N, b.M);
        REP(i, a.N) REP(j, b.M) REP(k, a.M){
            minimize(res.F[i][j], a.F[i][k] + b.F[k][j]);
        }
        return res;
    }
};

Matrix power(Matrix a, int exp){
    Matrix res; res.init(a.N, a.N);
    REP(i, a.N) res.F[i][i] = 1;

    for (; exp > 0; exp >>= 1, a = (a * a)) if(exp & 1){
        res = (res * a);
    }
    return res;
}

Matrix dp[MAX_NODE][17];

void process(void){
    cin >> k >> numNode >> numEdge >> numQuery;
    int n = (numNode - 1) / k;
    for (int i = 0; i <= n; ++i){
        for (int j = 0; j <= 16; ++j) dp[i][j].init(k, k);
    }
    for (int i = 1; i <= numEdge; ++i){
        int u, v, w; cin >> u >> v >> w;
        minimize(dp[u / k][0].F[u % k][v % k], w);
    }

    for (int k = 1; k < 16; ++k){
        for (int i = 0; i + MASK(k) - 1 <= n; ++i){
            dp[i][k] = dp[i][k - 1] * dp[i + MASK(k - 1)][k - 1];
        }
    }


    for (int i = 1; i <= numQuery; ++i){
        int u, v; cin >> u >> v;
        int l = u / k, r = v / k;
        int dif = r - l;
        Matrix res; res.init(k, k);
        REP(x, k) res.F[x][x] = 0;
        for (int j = 0; j < 16; ++j) if(BIT(dif, j)){
            res = res * dp[l][j];
            l |= MASK(j);
        }
        cout << (res.F[u % k][v % k] >= INF ? -1 : res.F[u % k][v % k]) << '\n';
    }
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);

    process();
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 87888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 88400 KB Output is correct
2 Correct 16 ms 33628 KB Output is correct
3 Correct 16 ms 33628 KB Output is correct
4 Correct 15 ms 33628 KB Output is correct
5 Correct 15 ms 33624 KB Output is correct
6 Correct 15 ms 33628 KB Output is correct
7 Correct 23 ms 34812 KB Output is correct
8 Correct 24 ms 34908 KB Output is correct
9 Correct 150 ms 87892 KB Output is correct
10 Correct 178 ms 84424 KB Output is correct
11 Correct 166 ms 88404 KB Output is correct
12 Correct 151 ms 83796 KB Output is correct
13 Correct 129 ms 72540 KB Output is correct
14 Correct 96 ms 64340 KB Output is correct
15 Correct 105 ms 71504 KB Output is correct
16 Correct 113 ms 71644 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33624 KB Output is correct
2 Incorrect 16 ms 33628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33624 KB Output is correct
2 Incorrect 16 ms 33628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 87888 KB Output isn't correct
2 Halted 0 ms 0 KB -