oj.uz

Submission #557556

# Submission time Handle Problem Language Result Execution time Memory
557556 2022-05-05T13:06:01 Z fatemetmhr Toll (BOI17_toll) C++17
7 / 100
 3000 ms 14872 KB 
// `Be name khoda` //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second


const int maxn5 = 2e5 + 10;
const int inf   = 1e9;

int dis[maxn5], prec[maxn5], no = 0, cmp[maxn5], h[maxn5];
vector <pair<int, int>> jda[maxn5], adj[maxn5];
bool mark[maxn5];

inline void dfs(int v){
    mark[v] = true;
    cmp[v] = no;
    for(auto [u, t] : adj[v]){
        h[u] = h[v] + t;
        dfs(u);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int k, n, m, q; cin >> k >> n >> m >> q;
    for(int i = 0; i < m; i++){
        int a, b, t; cin >> a >> b >> t;
        jda[b].pb({a, t});
        adj[a].pb({b, t});
    }
    fill(prec, prec + n + 5, inf);
    prec[0] = 0;
    for(int i = 0; i < n; i++) for(auto [u, t] : adj[i])
        prec[u] = min(prec[u], prec[i] + t);
    for(int i = 0; i < n; i++) if(prec[i] == inf)
        prec[i] = -1;
    for(int i = 0; i < n; i++) if(!mark[i]){
        dfs(i);
        no++;
    }
    for(int i = 0; i < q; i++){
        int a, b; cin >> a >> b;
        if(a == 0){
            cout << prec[b] << '\n';
            continue;
        }
        if(k == 1){
            if(cmp[a] == cmp[b])
                cout << h[b] - h[a] << '\n';
            else
                cout << -1 << '\n';
            continue;
        }
        fill(dis, dis + n + 4, inf);
        dis[b] = 0;
        for(int i = b; i > a; i--){
            for(auto [u, t] : jda[i])
                dis[u] = min(dis[u], dis[i] + t);
        }
        if(dis[a] == inf)
            dis[a] = -1;
        cout << dis[a] << '\n';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14872 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9708 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 29 ms 13488 KB Output is correct
9 Correct 31 ms 13340 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Execution timed out 3075 ms 9812 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Execution timed out 3075 ms 9812 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14872 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9708 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 29 ms 13488 KB Output is correct
9 Correct 31 ms 13340 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct
11 Execution timed out 3065 ms 13476 KB Time limit exceeded
12 Halted 0 ms 0 KB -