oj.uz

답안 #737527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
737527 2023-05-07T09:45:57 Z Ronin13 Relay Marathon (NOI20_relaymarathon) C++14
5 / 100
 6000 ms 846220 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> > 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){
        if(len < dp[u].back().f)
        dp[u].pb({len, x}), q.push({-len, {u, x}});
    }
    sort(dp[u].begin(), dp[u].end());
    if(dp[u].size() > bb)
        dp[u].pop_back();

}

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, 0});
    }
   // 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 'void upd(int, int, long long int)':
RelayMarathon.cpp:34:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(dp[u].size() > bb)
      |        ~~~~~~~~~~~~~^~~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:97: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]
   97 |     for(int i = 0; i < cand.size(); i++){
      |                    ~~^~~~~~~~~~~~~
RelayMarathon.cpp:98: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]
   98 |         for(int j =0; j < cand.size(); j++){
      |                       ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 17108 KB Output is correct
2 Correct 239 ms 17432 KB Output is correct
3 Correct 16 ms 17108 KB Output is correct
4 Correct 9 ms 17108 KB Output is correct
5 Correct 14 ms 17108 KB Output is correct
6 Correct 17 ms 17172 KB Output is correct
7 Correct 272 ms 17436 KB Output is correct
8 Correct 126 ms 17308 KB Output is correct
9 Correct 9 ms 17152 KB Output is correct
10 Correct 9 ms 17108 KB Output is correct
11 Correct 127 ms 17332 KB Output is correct
12 Correct 86 ms 17208 KB Output is correct
13 Correct 531 ms 17464 KB Output is correct
14 Correct 83 ms 17236 KB Output is correct
15 Correct 613 ms 17544 KB Output is correct
16 Correct 16 ms 17152 KB Output is correct
17 Correct 586 ms 17516 KB Output is correct
18 Correct 15 ms 17176 KB Output is correct
19 Correct 639 ms 17528 KB Output is correct
20 Correct 125 ms 17268 KB Output is correct
21 Correct 360 ms 17400 KB Output is correct
22 Correct 10 ms 17108 KB Output is correct
23 Correct 334 ms 17424 KB Output is correct
24 Correct 29 ms 17180 KB Output is correct
25 Correct 15 ms 17088 KB Output is correct
26 Correct 16 ms 17132 KB Output is correct
27 Correct 9 ms 17108 KB Output is correct
28 Correct 662 ms 17488 KB Output is correct
29 Correct 288 ms 17344 KB Output is correct
30 Correct 414 ms 17332 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 17108 KB Output is correct
2 Correct 239 ms 17432 KB Output is correct
3 Correct 16 ms 17108 KB Output is correct
4 Correct 9 ms 17108 KB Output is correct
5 Correct 14 ms 17108 KB Output is correct
6 Correct 17 ms 17172 KB Output is correct
7 Correct 272 ms 17436 KB Output is correct
8 Correct 126 ms 17308 KB Output is correct
9 Correct 9 ms 17152 KB Output is correct
10 Correct 9 ms 17108 KB Output is correct
11 Correct 127 ms 17332 KB Output is correct
12 Correct 86 ms 17208 KB Output is correct
13 Correct 531 ms 17464 KB Output is correct
14 Correct 83 ms 17236 KB Output is correct
15 Correct 613 ms 17544 KB Output is correct
16 Correct 16 ms 17152 KB Output is correct
17 Correct 586 ms 17516 KB Output is correct
18 Correct 15 ms 17176 KB Output is correct
19 Correct 639 ms 17528 KB Output is correct
20 Correct 125 ms 17268 KB Output is correct
21 Correct 360 ms 17400 KB Output is correct
22 Correct 10 ms 17108 KB Output is correct
23 Correct 334 ms 17424 KB Output is correct
24 Correct 29 ms 17180 KB Output is correct
25 Correct 15 ms 17088 KB Output is correct
26 Correct 16 ms 17132 KB Output is correct
27 Correct 9 ms 17108 KB Output is correct
28 Correct 662 ms 17488 KB Output is correct
29 Correct 288 ms 17344 KB Output is correct
30 Correct 414 ms 17332 KB Output is correct
31 Incorrect 33 ms 20820 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6137 ms 846220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 17108 KB Output is correct
2 Correct 239 ms 17432 KB Output is correct
3 Correct 16 ms 17108 KB Output is correct
4 Correct 9 ms 17108 KB Output is correct
5 Correct 14 ms 17108 KB Output is correct
6 Correct 17 ms 17172 KB Output is correct
7 Correct 272 ms 17436 KB Output is correct
8 Correct 126 ms 17308 KB Output is correct
9 Correct 9 ms 17152 KB Output is correct
10 Correct 9 ms 17108 KB Output is correct
11 Correct 127 ms 17332 KB Output is correct
12 Correct 86 ms 17208 KB Output is correct
13 Correct 531 ms 17464 KB Output is correct
14 Correct 83 ms 17236 KB Output is correct
15 Correct 613 ms 17544 KB Output is correct
16 Correct 16 ms 17152 KB Output is correct
17 Correct 586 ms 17516 KB Output is correct
18 Correct 15 ms 17176 KB Output is correct
19 Correct 639 ms 17528 KB Output is correct
20 Correct 125 ms 17268 KB Output is correct
21 Correct 360 ms 17400 KB Output is correct
22 Correct 10 ms 17108 KB Output is correct
23 Correct 334 ms 17424 KB Output is correct
24 Correct 29 ms 17180 KB Output is correct
25 Correct 15 ms 17088 KB Output is correct
26 Correct 16 ms 17132 KB Output is correct
27 Correct 9 ms 17108 KB Output is correct
28 Correct 662 ms 17488 KB Output is correct
29 Correct 288 ms 17344 KB Output is correct
30 Correct 414 ms 17332 KB Output is correct
31 Incorrect 33 ms 20820 KB Output isn't correct
32 Halted 0 ms 0 KB -