oj.uz

Submission #757931

# Submission time Handle Problem Language Result Execution time Memory
757931 2023-06-14T02:11:19 Z ProtonDecay314 Voting Cities (NOI22_votingcity) C++17
20 / 100
 17 ms 1240 KB 
/*
Time complexity: O(Q + (N + E)log E)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector<tuple<ll, ll>>> adjl_ll;

class CompTuple {
    public:
        bool operator()(tuple<ll, ll> a, tuple<ll, ll> b) {
            return get<1>(a) > get<1>(b);
        }
};

vector<ll> get_min_dists(ll N, ll E, const vector<ll>& voting, const adjl_ll& out_e, const adjl_ll& in_e) {
    vector<bool> vis(N, false);
    priority_queue<tuple<ll, ll>, vector<tuple<ll, ll>>, CompTuple> pq;

    for(const ll& k : voting) {
        pq.push({k, 0ll});
    }

    vector<ll> dists(N, -1ll);
    
    while(!pq.empty()) {
        ll curnode, curdist;
        tie(curnode, curdist) = pq.top();
        pq.pop();

        if(vis[curnode]) continue;
        vis[curnode] = true;
        dists[curnode] = curdist;

        for(const tuple<ll, ll>& edge : in_e[curnode]) {
            pq.push({get<0>(edge), curdist + get<1>(edge)});
        }
    }

    return dists;
}

ll solve(ll N, ll E, const vector<ll>& voting, const adjl_ll& out_e, const adjl_ll& in_e, ll S, const vector<ll>& p) {
    // vector<bool> vis(N, false);
    // priority_queue<tuple<ll, ll>, vector<tuple<ll, ll>>, CompTuple> pq;

    // for(const ll& k : voting) {
    //     pq.push({k, 0ll});
    // }


    // while(!pq.empty()) {
    //     ll curnode, curdist;
    //     tie(curnode, curdist) = pq.top();
    //     pq.pop();

    //     if(vis[curnode]) continue;
    //     vis[curnode] = true;
    // }
    // TODO
    return 0ll;
}

int main() {
    ll N, E, K;
    cin >> N >> E >> K;

    vector<ll> voting(K, 0);
    for(ll& v : voting) {
        cin >> v;
    }
    
    adjl_ll out_e;
    adjl_ll in_e;
    for(ll i = 0ll; i < N; i++) {
        vector<tuple<ll, ll>> adj_out;
        vector<tuple<ll, ll>> adj_in;

        out_e.push_back(adj_out);
        in_e.push_back(adj_in);
    }

    for(ll i = 0ll; i < E; i++) {
        ll u, v, c;
        cin >> u >> v >> c;
        out_e[u].push_back({v, c});
        in_e[v].push_back({u, c});
    }

    ll Q;
    cin >> Q;

    vector<ll> dists = get_min_dists(N, E, voting, out_e, in_e);
    while(Q--) {
        ll S;
        vector<ll> p(5, 0ll);
        cin >> S >> p[0] >> p[1] >> p[2] >> p[3] >> p[4];

        cout << dists[S] << endl;
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1124 KB Output is correct
2 Correct 7 ms 872 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1124 KB Output is correct
2 Correct 7 ms 872 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 11 ms 1096 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1080 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1124 KB Output is correct
2 Correct 7 ms 872 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 11 ms 1096 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1080 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 17 ms 1236 KB Output is correct
12 Correct 7 ms 852 KB Output is correct
13 Correct 14 ms 1240 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1124 KB Output is correct
2 Correct 7 ms 872 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 11 ms 996 KB Output is correct
7 Correct 6 ms 816 KB Output is correct
8 Correct 11 ms 1072 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1124 KB Output is correct
2 Correct 7 ms 872 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 11 ms 1096 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1080 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 11 ms 996 KB Output is correct
12 Correct 6 ms 816 KB Output is correct
13 Correct 11 ms 1072 KB Output is correct
14 Incorrect 12 ms 1140 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 15.0

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

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1124 KB Output is correct
2 Correct 7 ms 872 KB Output is correct
3 Correct 12 ms 1116 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 11 ms 1096 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 13 ms 1080 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 17 ms 1236 KB Output is correct
12 Correct 7 ms 852 KB Output is correct
13 Correct 14 ms 1240 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 11 ms 996 KB Output is correct
17 Correct 6 ms 816 KB Output is correct
18 Correct 11 ms 1072 KB Output is correct
19 Incorrect 12 ms 1140 KB Output isn't correct
20 Halted 0 ms 0 KB -