oj.uz

Submission #1016441

# Submission time Handle Problem Language Result Execution time Memory
1016441 2024-07-08T05:16:43 Z Whisper Toll (BOI17_toll) C++17
10 / 100
 175 ms 85440 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.M);
    REP(i, a.N) res.F[i][i] = 0;

    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 168 ms 84728 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 153 ms 85328 KB Output is correct
2 Correct 7 ms 33624 KB Output is correct
3 Correct 6 ms 33628 KB Output is correct
4 Correct 6 ms 33696 KB Output is correct
5 Correct 6 ms 33628 KB Output is correct
6 Correct 6 ms 33680 KB Output is correct
7 Correct 12 ms 34652 KB Output is correct
8 Correct 14 ms 34852 KB Output is correct
9 Correct 175 ms 84564 KB Output is correct
10 Correct 158 ms 81748 KB Output is correct
11 Correct 156 ms 85440 KB Output is correct
12 Correct 161 ms 80888 KB Output is correct
13 Correct 112 ms 70564 KB Output is correct
14 Correct 88 ms 62712 KB Output is correct
15 Correct 94 ms 69488 KB Output is correct
16 Correct 99 ms 69300 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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