oj.uz

Submission #737528

# Submission time Handle Problem Language Result Execution time Memory
737528 2023-05-07T09:49:01 Z Ronin13 Relay Marathon (NOI20_relaymarathon) C++14
0 / 100
 6000 ms 1048576 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 = 5000;
vector <vector <pll> > dp(nmax);
map <pii, bool> used;
vector <vector <pll> > g(nmax);
priority_queue <pair<ll, pii> > q;
void upd(int u, int x, ll len){
    bool tt;
    tt = false;
    for(int j = 0; j < bb; j++){
        if(dp[u][j].s == x){
            tt = true;
            if(len > dp[u][j].f) continue;
            dp[u][j].f = len;
            q.push({-dp[u][j].f, {u, dp[u][j].s}});
        }
    }
    if(!tt){
        dp[u].pop_back();
        dp[u].pb({len, x}), q.push({-len, {u, x}});
    }
    sort(dp[u].begin(), dp[u].end());


}

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);
    }
   // cout << 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < bb; j++)
        dp[i].pb({1e18, -j});
    }
   // cout << 1;
    for(int to : sources){
        dp[to][0] = {0, to};
        q.push({0, {to, to}});
    }
    //cout << 1;
    while(!q.empty()){
        int v = q.top().s.f, y = q.top().s.s;
        ll val = -q.top().f;
        q.pop();
        if(used[{v, y}]) continue;
        used[{v, y}] = true;
        for(auto ed : g[v]){
            int to = ed.f;
            ll len = ed.s + val;
            upd(to, y, len);
        }
    }
    vector <pair<ll, pii> > vec;
    for(int to : sources){
        for(int j = 0; j < bb; j++){
            if(dp[to][j].f != 1e18)
            vec.pb({dp[to][j].f, {to, dp[to][j].s}});
        }
    }
    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(cnt[to.s.f] < k && cnt[to.s.s] < k){
            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:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> >, std::allocator<std::pair<long long int, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0; i < cand.size(); i++){
      |                    ~~^~~~~~~~~~~~~
RelayMarathon.cpp:97:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> >, std::allocator<std::pair<long long int, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int j =0; j < cand.size(); j++){
      |                       ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 20884 KB Output is correct
2 Correct 5325 ms 21080 KB Output is correct
3 Correct 307 ms 20876 KB Output is correct
4 Correct 14 ms 20892 KB Output is correct
5 Correct 183 ms 20876 KB Output is correct
6 Correct 368 ms 20940 KB Output is correct
7 Execution timed out 6085 ms 20952 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 20884 KB Output is correct
2 Correct 5325 ms 21080 KB Output is correct
3 Correct 307 ms 20876 KB Output is correct
4 Correct 14 ms 20892 KB Output is correct
5 Correct 183 ms 20876 KB Output is correct
6 Correct 368 ms 20940 KB Output is correct
7 Execution timed out 6085 ms 20952 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1113 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 20884 KB Output is correct
2 Correct 5325 ms 21080 KB Output is correct
3 Correct 307 ms 20876 KB Output is correct
4 Correct 14 ms 20892 KB Output is correct
5 Correct 183 ms 20876 KB Output is correct
6 Correct 368 ms 20940 KB Output is correct
7 Execution timed out 6085 ms 20952 KB Time limit exceeded
8 Halted 0 ms 0 KB -