oj.uz

Submission #628036

# Submission time Handle Problem Language Result Execution time Memory
628036 2022-08-13T03:46:12 Z vbee Toll (BOI17_toll) C++14
10 / 100
 55 ms 6728 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define TASK "simproads"
#define pb push_back
#define all(r) (r).begin(), (r).end()
#define ll long long
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x) >> (i) & 1)

using namespace std;

const int LOG = 19;
const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 5e4 + 7;

int n, k, m, q, pre[N], dist[N];
vector<pair<int, int>> g[N], queries;

void dijkstra(int root){
    for (int i = 1; i <= n; i++) dist[i] = oo;
    dist[root] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> kew;
    kew.push({0, root});
    while (!kew.empty()){
        auto k = kew.top();
        kew.pop();
        if (k.fi > dist[k.se]) continue;
        for (auto u : g[k.se]){
            if (u.se + k.fi < dist[u.fi]){
                dist[u.fi] = u.se + k.fi;
                kew.push({dist[u.fi], u.fi});
            }
        }
    }
}
struct DSU{
    vector<int> par, sz;
    int n;
    DSU(int _n){
        n = _n;
        par.resize(n + 7);
        sz.resize(n + 7);
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find_node(int u){
        if (u == par[u]) return u;
        else return par[u] = find_node(par[u]);
    }

    bool unify(int u, int v){
        u = find_node(u);
        v = find_node(v);
        if (u == v) return false;
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        return true;
    }

    bool same(int u, int v) {
        if (find_node(u) == find_node(v)) return true;
        return false;
    }
};
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdout);
    cin >> k >> n >> m >> q;
    for (int i = 1; i <= m; i++){
        int u, v, c; cin >> u >> v >> c;
        u++; v++;
        g[u].pb({v, c});
    }
    bool flag = true;
    for (int i = 1; i <= q; i++){
        int u, v; cin >> u >> v;
        u++; v++;
        if (u != 1) flag = false;
        queries.pb({u, v});
    }
    if (k == 1){
        for (int i = 1; i <= n; i++) {
            pre[i] += pre[i - 1];
            if (g[i].size()) pre[i + 1] += g[i][0].se;
        }
        DSU dsu(n);
        for (int i = 1; i <= n; i++){
            if (g[i].size()) dsu.unify(i, i + 1);
        }
        for (int i = 0; i < queries.size(); i++){
            int u = queries[i].fi, v = queries[i].se;
            if (!dsu.same(u, v)) cout << -1 << "\n";
            else cout << pre[max(u, v)] - pre[min(u, v) - 1] << "\n";
        }
    }
    else if (flag){
        dijkstra(1);
        for (auto u : queries){
            if (dist[u.se] == oo) cout << -1 << "\n";
            else cout << dist[u.se] << "\n";
        }
    }
    else if (q <= 100){
        for (auto u : queries){
            dijkstra(u.fi);
            if (dist[u.se] == oo) cout << -1 << "\n";
            else cout << dist[u.se] <<"\n";
        }
    }
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int i = 0; i < queries.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3924 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 31 ms 3464 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1496 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 3 ms 1748 KB Output is correct
8 Correct 3 ms 1876 KB Output is correct
9 Correct 19 ms 4756 KB Output is correct
10 Correct 55 ms 6616 KB Output is correct
11 Correct 48 ms 5188 KB Output is correct
12 Correct 28 ms 4564 KB Output is correct
13 Correct 54 ms 6728 KB Output is correct
14 Correct 33 ms 4800 KB Output is correct
15 Correct 27 ms 4176 KB Output is correct
16 Correct 33 ms 4104 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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