oj.uz

답안 #1016431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016431 2024-07-08T05:08:04 Z Whisper Toll (BOI17_toll) C++17
10 / 100
 193 ms 88656 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 = 15; j >= 0; --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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 166 ms 87800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 88400 KB Output is correct
2 Correct 15 ms 33628 KB Output is correct
3 Correct 15 ms 33624 KB Output is correct
4 Correct 14 ms 33544 KB Output is correct
5 Correct 14 ms 33624 KB Output is correct
6 Correct 15 ms 33504 KB Output is correct
7 Correct 21 ms 34652 KB Output is correct
8 Correct 24 ms 34904 KB Output is correct
9 Correct 161 ms 87636 KB Output is correct
10 Correct 172 ms 84796 KB Output is correct
11 Correct 193 ms 88656 KB Output is correct
12 Correct 153 ms 83768 KB Output is correct
13 Correct 125 ms 72784 KB Output is correct
14 Correct 96 ms 64336 KB Output is correct
15 Correct 108 ms 71508 KB Output is correct
16 Correct 118 ms 71576 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 33628 KB Output is correct
2 Correct 16 ms 33632 KB Output is correct
3 Correct 15 ms 33624 KB Output is correct
4 Correct 15 ms 33628 KB Output is correct
5 Correct 17 ms 33628 KB Output is correct
6 Incorrect 17 ms 34652 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 33628 KB Output is correct
2 Correct 16 ms 33632 KB Output is correct
3 Correct 15 ms 33624 KB Output is correct
4 Correct 15 ms 33628 KB Output is correct
5 Correct 17 ms 33628 KB Output is correct
6 Incorrect 17 ms 34652 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 166 ms 87800 KB Output isn't correct
2 Halted 0 ms 0 KB -