oj.uz

Submission #758959

# Submission time Handle Problem Language Result Execution time Memory
758959 2023-06-15T15:17:58 Z Dexva Voting Cities (NOI22_votingcity) C++14
20 / 100
 5 ms 1236 KB 
#include <bits/stdc++.h>
using namespace std;

#define lln long long
const long long INF = numeric_limits<long long>::max();
using pll = pair<long,long>;

void solve() {
    lln N, E, K; cin >> N >> E >> K;
    vector<lln> cities(N+1), vcities(K); //cities are 0-indexed,, 1 city will be the mega target (coalsced voting cities)
    vector<pll> roads(E);
    map<lln, vector<pll> > adj;
    
    for (lln i=0;i<K;i++) cin >> vcities[i]; //list of voting cities
    for (lln i=0;i<E;i++) {
        lln u, v, c; cin >> u >> v >> c; //we reverse the graph so instead of u->v, v-> u (see notes for subtask 2)
        adj[v].push_back({u,c});
    }

    //connecting mega target (which is city `N`)
    for (auto& vc : vcities) adj[N].push_back({vc,0});

    //dijkstra proper
    vector<lln> d(N+1,INF);
    vector<bool> done(N+1,false);
    lln source = N;
    priority_queue<pll, vector<pll>, greater<pll> > pq;

    pq.push({0, source});  // first parameter of pll is the distance/total weight, second parameter is index
    d[source] = 0;

    while(!pq.empty()) {
        // for (auto& k : d) cout << k << " ";
        // cout << '\n';

        pll k = pq.top(); pq.pop();
        lln city = k.second;
        if (!done[city]) {
            for(auto& [to, cost] : adj[city]) {
                if (d[to]>d[city]+cost) {
                    d[to] = d[city] + cost;
                    pq.push({d[to], to});
                }
            }
            done[city] = true;
        }
    }

    // cout << "\n Edge List: \n";
    // for (auto& p : adj) {
    //     lln city = p.first; vector<pll> neighbors = p.second;
    //     printf("source %lld | ", city);
    //     for (pll n : neighbors) printf("(%lld, %lld) ", n.first, n.second);
    //     printf("\n");
    //     // cout << k << " ";
    // }
    // cout << '\n';

    // cout << "\nDijkstra output: \n";
    // for (auto& k : d) cout << k << " ";
    // cout << '\n';

    //Queries stuff
    lln Q; cin >> Q;
    for (lln q=0;q<Q;q++) {
        lln asked; cin >> asked;
        vector<lln> tickets(5);
        for (lln i=0;i<5;i++) cin >> tickets[i];
        if (d[asked]==INF) cout << -1 << '\n';
        else cout << d[asked] << '\n';
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lln t = 1;
    while (t--) solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:39:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |             for(auto& [to, cost] : adj[city]) {
      |                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 5 ms 1236 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 5 ms 1108 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Incorrect 5 ms 1232 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 15.0

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

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1168 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 5 ms 1236 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 5 ms 1108 KB Output is correct
17 Correct 3 ms 980 KB Output is correct
18 Correct 5 ms 1236 KB Output is correct
19 Incorrect 5 ms 1232 KB Output isn't correct
20 Halted 0 ms 0 KB -