oj.uz

Submission #854135

# Submission time Handle Problem Language Result Execution time Memory
854135 2023-09-26T08:19:07 Z ancuber1031 Robot (JOI21_ho_t4) C++14
0 / 100
 275 ms 24124 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define p_q priority_queue
#define endl '\n'
#define pb push_back

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; cin>>n>>m;    
    vector<vector<tuple<int,int,int> > > g(n+2);
    for (int i = 1; i <= m; ++i) {
        int u, v, c, p;
        cin>>u>>v>>c>>p;
        g[u].pb({v,c,p});
        g[v].pb({u,c,p});
    }
    for (int i = 1; i <= n; ++i) {
        map<int,int> cnt, sm;
        for (auto& [v,c,p] : g[i]) {
            cnt[c]++;
            sm[c] += p;
        }
        for (auto& [v,c,p] : g[i]) {
            if (cnt[c] == 1) p = 0;
            else p = min(p,sm[c]-p);
        }
    }
    p_q <pii,vector<pii>,greater<pii>> pq;
    vector<int> dis(n+2,2e18), vis(n+2,0);
    dis[1] = 0;
    pq.push({0,1});
    while(!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();
        if (vis[cur]) continue;
        vis[cur] = 1;
        for (auto& [v,c,p] : g[cur]) {
            if (dis[cur]+p < dis[v]) {
                dis[v] = dis[cur]+p;
                pq.push({dis[v],v});
            }
        }
    }
    if (dis[n] >= 1e18) cout<<-1<<endl;
    else cout<<dis[n]<<endl;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:23:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         for (auto& [v,c,p] : g[i]) {
      |                    ^
Main.cpp:27:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |         for (auto& [v,c,p] : g[i]) {
      |                    ^
Main.cpp:41:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for (auto& [v,c,p] : g[cur]) {
      |                    ^

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Incorrect 2 ms 600 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9164 KB Output is correct
2 Correct 19 ms 4696 KB Output is correct
3 Correct 56 ms 14416 KB Output is correct
4 Correct 26 ms 6484 KB Output is correct
5 Incorrect 275 ms 24124 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Incorrect 2 ms 600 KB Output isn't correct
10 Halted 0 ms 0 KB -