oj.uz

Submission #667230

# Submission time Handle Problem Language Result Execution time Memory
667230 2022-11-30T21:03:43 Z Sogol Toll (BOI17_toll) C++17
0 / 100
 3000 ms 226668 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
 
#define pb       push_back
#define Sz(x)    int((x).size())
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
 
const int maxn  =  1e6   + 10;
const int maxa  =  2e9   +  5;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;
const double eps = 1e-9;

int a[maxn], b[maxn], dp[10][maxn], pd[10][maxn], ans[maxn], n, k, bl;
vector <pair <int, int> > adj[maxn], ajd[maxn];
vector <int> qu[4 * maxn];

void avocado(int nd = 1, int s = 0, int e = bl){
    if (e - s == 1) return;
    int mid = (s + e) / 2, lc = 2 * nd, rc = lc + 1;
    avocado(lc, s, mid);
    avocado(rc, mid, e);
    memset(dp, 60, sizeof(dp));
    memset(pd, 60, sizeof(pd));
    for (int i = 0; i < k; i ++){
        int v = mid * k + i;
        if(v >= n) break;
        dp[i][v] = 0;
        for (int j = v; j < k * e; j ++){
            for (auto p : adj[j]){ 
                int u = p.fi, w = p.se;
                dp[i][u] = min(dp[i][u], dp[i][j] + w);
            }
        }
        pd[i][v] = 0;
        for (int j = v; j >= s * k; j --){
            for (auto p : ajd[j]){
                int u = p.fi, w = p.se;
                pd[i][u] = min(pd[i][u], pd[i][j] + w);
            }
        }
        for (int x : qu[nd]){
            ans[x] = mod;
            for (int i = 0; i < k; i ++){
                ans[x] = min(ans[x], pd[i][a[x]] + dp[i][b[x]]);
            }
        }
    }
    return;
}

int find(int l, int r, int v = 1, int s = 0, int e = bl){
    if(e - s == 1) return v;
    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
    if(r < mid) return find(l, r, lc, s, mid);
    if(mid < l) return find(l, r, rc, mid, e);
    return v;
}

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int m, o;
    cin >> k >> n >> m >> o;
    bl = (n + k - 1) / k;
    for (int i = 0; i < m; i ++){
        int v, u, t;
        cin >> v >> u >> t;
        adj[v].pb({u, t});
        ajd[u].pb({v, t});
    }
    memset(ans, 60, sizeof(ans));
    for (int i = 0; i < o; i ++){
        cin >> a[i] >> b[i];
        if(a[i] > b[i]) continue;
        qu[find(a[i] / k, b[i] / k + 1)].pb(i);
    }
    avocado();
    for (int i = 0; i < o; i ++) cout << (ans[i] >= mod ? -1 : ans[i]) << '\n';
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 226668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 226572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 226668 KB Time limit exceeded
2 Halted 0 ms 0 KB -