oj.uz

Submission #777293

# Submission time Handle Problem Language Result Execution time Memory
777293 2023-07-09T02:00:48 Z Alora Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 57988 KB 
#include <bits/stdc++.h>
#define name "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define pb push_back
#define all(v) v.begin(), v.end()
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int n, m;
struct dl{
    ll h;
    int a, b;
    bool operator < (const dl &o) const {return h > o.h;}
};
vector <dl> g[maxn];

ll cost[1003][2003], dp[1003][2003];
void sub1(){
    set <int> luu[1003];
    fi(i, 1, n){
        luu[i].insert(0);
        for(auto [j, cl, p]: g[i]){
            cost[i][cl] += p;
            luu[i].insert(cl);
        }
    }
    fi(i, 1, n)
        fi(j, 0, m) dp[i][j] = 1e18;
    priority_queue <dl> q;
    dp[1][0] = 0;
    q.push({0, 1, 0});
    while(q.size()){
        auto [h, u, x] = q.top(); q.pop();
        if(h != dp[u][x]) continue;
        fi(i, 1, m){
            for(auto [v, cl, p]: g[u]){
                if(cl == i){
                    if(dp[v][i] > h + cost[u][i] - p){
                        dp[v][i] = h + cost[u][i] - p;
                        q.push({dp[v][i], v, i});
                    }
                }
                else{
                    if(dp[v][i] > h + cost[u][i] + p){
                        dp[v][i] = h + cost[u][i] + p;
                        q.push({dp[v][i], v, i});
                    }
                }
            }
        }
    }
    ll res = 1e18;
    fi(i, 1, m) res = min(res, dp[n][i]);
    if(res != 1e18) cout << res;
    else cout << -1;
    exit(0);
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
//    freopen(name".in", "r", stdin);
 //   freopen(name".out", "w", stdout);
    cin >> n >> m;
    fi(i, 1, m){
        int u, v, c, p; cin >> u >> v >> c >> p;
        g[u].pb({v, c, p});
        g[v].pb({u, c, p});
    }
    if(n <= 1000 && m <= 2000) sub1();
}

Compilation message

Main.cpp: In function 'void sub1()':
Main.cpp:46:43: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   46 |                         q.push({dp[v][i], v, i});
      |                                           ^
Main.cpp:52:43: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   52 |                         q.push({dp[v][i], v, i});
      |                                           ^

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5104 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 7 ms 5976 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 1317 ms 10692 KB Output is correct
8 Correct 240 ms 6852 KB Output is correct
9 Execution timed out 3079 ms 57988 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5104 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 7 ms 5976 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 1317 ms 10692 KB Output is correct
8 Correct 240 ms 6852 KB Output is correct
9 Execution timed out 3079 ms 57988 KB Time limit exceeded
10 Halted 0 ms 0 KB -