oj.uz

Submission #737554

# Submission time Handle Problem Language Result Execution time Memory
737554 2023-05-07T10:47:32 Z Ronin13 Relay Marathon (NOI20_relaymarathon) C++14
5 / 100
 6000 ms 139140 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 300001;
vector <ll> bit(nmax);
int bb = 500;
vector <vector <pll> > g(nmax);

int main(){
    int n, k, m; cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        ll w; cin >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    vector <int> sources;
    for(int i = 1 ;i <= k; i++){
        int x; cin >> x;
        sources.pb(x);
    }
    vector <vector <pair<ll, int> > > G(n + 1);
    for(int s : sources){
        priority_queue <pll> q;
        vector <ll> d(n + 1, 1e18);
        vector <bool> used(n + 1, false);
        q.push({0, s});
        d[s] = 0;
        while(!q.empty()){
            int v = q.top().s;
            q.pop();
            if(used[v]) continue;
            used[v] = true;
            for(auto x : g[v]){
                int to =x.f;
                ll len = x.s;
                if(d[to] > d[v] + len){
                    d[to] = d[v] + len;
                    q.push({-d[to], to});
                }
            }
        }
        vector <pll> vec;
        for(auto to : sources){
            vec.epb(d[to], to);
        }
        sort(vec.begin(), vec.end());
        for(int j = 0; j < min(k, bb); j++){
            G[s].pb(vec[j]);
        }
    }
    vector <pair<ll, pii> > vec;
    for(int i = 1; i <= n; i++){
        for(auto to : G[i]){
            vec.pb({to.f, {to.s, i}});
        }
    }
    sort(vec.begin(), vec.end());
    int cnt[n + 1];
    fill(cnt, cnt + n + 1, 0);
    vector <pair<ll, pii> > cand;
    for(auto to : vec){
        if(cand.size() > 100) break;
        if(cnt[to.s.f] < bb && cnt[to.s.s] < bb){
            cand.pb(to);
            cnt[to.s.f]++;
            cnt[to.s.s]++;
        }
    }
   // cout << 1;
    ll ans = 1e18;
    for(int i = 0; i < cand.size(); i++){
        for(int j =0; j < cand.size(); j++){
            set <int> st;
            st.insert(cand[i].s.f);
            st.insert(cand[i].s.s);
            st.insert(cand[j].s.f);
            st.insert(cand[j].s.s);
            if(st.size() == 4){
                ans = min(ans, cand[i].f + cand[j].f);
            }
        }
    }
    cout << ans;
    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9632 KB Output is correct
2 Correct 7 ms 9716 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 9 ms 9732 KB Output is correct
8 Correct 9 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9664 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 8 ms 9936 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 7 ms 9776 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 8 ms 9844 KB Output is correct
20 Correct 8 ms 9684 KB Output is correct
21 Correct 7 ms 9808 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 7 ms 9812 KB Output is correct
24 Correct 8 ms 9684 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 6 ms 9684 KB Output is correct
27 Correct 6 ms 9684 KB Output is correct
28 Correct 7 ms 9812 KB Output is correct
29 Correct 7 ms 9700 KB Output is correct
30 Correct 7 ms 9780 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9632 KB Output is correct
2 Correct 7 ms 9716 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 9 ms 9732 KB Output is correct
8 Correct 9 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9664 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 8 ms 9936 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 7 ms 9776 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 8 ms 9844 KB Output is correct
20 Correct 8 ms 9684 KB Output is correct
21 Correct 7 ms 9808 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 7 ms 9812 KB Output is correct
24 Correct 8 ms 9684 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 6 ms 9684 KB Output is correct
27 Correct 6 ms 9684 KB Output is correct
28 Correct 7 ms 9812 KB Output is correct
29 Correct 7 ms 9700 KB Output is correct
30 Correct 7 ms 9780 KB Output is correct
31 Correct 6 ms 9696 KB Output is correct
32 Correct 8 ms 9684 KB Output is correct
33 Correct 6 ms 9684 KB Output is correct
34 Correct 6 ms 9684 KB Output is correct
35 Correct 5 ms 9684 KB Output is correct
36 Incorrect 64 ms 14480 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 17204 KB Output is correct
2 Correct 18 ms 13636 KB Output is correct
3 Execution timed out 6025 ms 139140 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9632 KB Output is correct
2 Correct 7 ms 9716 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 9 ms 9732 KB Output is correct
8 Correct 9 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9664 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 8 ms 9936 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 7 ms 9776 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 8 ms 9844 KB Output is correct
20 Correct 8 ms 9684 KB Output is correct
21 Correct 7 ms 9808 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 7 ms 9812 KB Output is correct
24 Correct 8 ms 9684 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 6 ms 9684 KB Output is correct
27 Correct 6 ms 9684 KB Output is correct
28 Correct 7 ms 9812 KB Output is correct
29 Correct 7 ms 9700 KB Output is correct
30 Correct 7 ms 9780 KB Output is correct
31 Correct 6 ms 9696 KB Output is correct
32 Correct 8 ms 9684 KB Output is correct
33 Correct 6 ms 9684 KB Output is correct
34 Correct 6 ms 9684 KB Output is correct
35 Correct 5 ms 9684 KB Output is correct
36 Incorrect 64 ms 14480 KB Output isn't correct
37 Halted 0 ms 0 KB -