oj.uz

Submission #675052

# Submission time Handle Problem Language Result Execution time Memory
675052 2022-12-26T22:29:05 Z Trent Toll (BOI17_toll) C++17
0 / 100
 123 ms 21256 KB 
#include "bits/stdc++.h"
#include <cstring>
#include <fstream>

using namespace std;

#define ll long long
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define open(s) freopen(((string) s + ".in").c_str(), "r", stdin); freopen(((string) s + ".out").c_str(), "w", stdout)
#define all(i) i.begin(), i.end()
#define boost() cin.sync_with_stdio(0); cin.tie()
typedef pair<int, int> pii;

const int MN = 5e4 + 10, MK = 5, ME = 17, INF = 5e8 + 10;
struct edge{int i, w;};
int dis[MN][ME][MK];
vector<edge> adj[MN];
int k, n, m, o;

inline int st(int a){
    return k + a / k * k;
}

signed main() {
    cin >> k >> n >> m >> o;
    forR(a, MN) forR(b, ME) forR(c, MK) dis[a][b][c] = INF;

    forR(g, m){
        int a, b, t; cin >> a >> b >> t;
        dis[a][0][b - st(a)] = t;
        adj[a].push_back({b, t});
    }
    REP(e, 1, ME) forR(i, n) forR(t, k){
        dis[i][e][t] = INF;
        forR(m, k) dis[i][e][t] = min(dis[i][e][t], dis[i][e-1][m] + dis[st(i) + m][e-1][t]);
    }
    forR(g, o){
        int a, b; cin >> a >> b;
        int amt = b / k - a / k;
        vector<int> mi(5, INF);
        mi[a % k] = 0;
        for(int c=a / k, e = ME - 1; e >= 0; --e) if((1 << e) <= amt){
            vector<int> nex(5, INF);
            forR(st, k) forR(en, k) nex[en] = min(nex[en], mi[st] + dis[k * c + st][e][en]);
            mi.swap(nex);
            c += 1 << e;
            amt -= (1 << e);
        }
        if(mi[b % k] == INF) cout << "-1\n";
        else cout << mi[b % k] << '\n';
    }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18032 KB Output is correct
2 Correct 9 ms 18004 KB Output is correct
3 Correct 9 ms 17996 KB Output is correct
4 Correct 9 ms 18004 KB Output is correct
5 Correct 9 ms 18004 KB Output is correct
6 Incorrect 11 ms 18132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18032 KB Output is correct
2 Correct 9 ms 18004 KB Output is correct
3 Correct 9 ms 17996 KB Output is correct
4 Correct 9 ms 18004 KB Output is correct
5 Correct 9 ms 18004 KB Output is correct
6 Incorrect 11 ms 18132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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