oj.uz

Submission #775630

# Submission time Handle Problem Language Result Execution time Memory
775630 2023-07-06T16:28:51 Z Filya Robot (JOI21_ho_t4) C++14
100 / 100
 1574 ms 129020 KB 
//♥God will make a way♥
 
//#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <set>
#include <map>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stdio.h>
#include <climits>
#include <numeric>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/////////////////////define/////////////////////
#define ci(x) if(x) cout << "YES" << '\n'; else cout << "NO" << '\n';
#define cii(x) if(check(x))
#define MOD 1000000007
#define MOD2 998244353
#define oo 1e9
#define ool 1e18L
#define pii pair<int, int>
#define pll pair<long long, long long>
#define mii map<int, int>
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define vll vector <ll>
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define alll(x) (x), (x) + n
#define clr(x) (x).clear();
#define fri(x) for(int i = 0; i < x; ++i)
#define frj(x) for(int j = 0; j < x; ++j)
#define frp(x) for(int p = 0; p < x; ++p)
#define frr(a, b) for(int i = a; i < b; ++i)
#define frrj(a, b) for(int j = a; j < b; ++j)
#define fra(x) for(int i = 0; i < x; ++i) cin >> a[i];
#define frb(x) for(int i = 0; i < x; ++i) cin >> b[i];
#define frs(x) for(auto it = x.begin(); it != x.end(); ++it)
#define fr(x) for(auto it : x) //el
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define dbg(x) cerr << #x << ": " << x << endl;
#define ce(x) cout << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin()); //make all one after sorting
#define blt __builtin_popcount
/////////////////////print array, vector, deque, set, multiset, pair, map /////////////////////
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]"; cout << endl;}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(stack <T> v) {cerr << "[ "; stack<T> s = v; while(s.size()) {T i = s.top(); print(i); s.pop(); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(queue <T> v) {cerr << "[ "; queue<T> s = v; while(s.size()) {T i = s.front(); print(i); s.pop(); cerr << " ";} cerr << "]"; cout << endl;}
template <class T> void print(deque <T> v) {cerr << "[ "; deque<T> s = v; while(s.size()) {T i = s.front(); print(i); s.pop_front(); cerr << " ";} cerr << "]"; cout << endl;}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
template <class T, class V> void print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]"; cout << endl;}
/////////////////////de/////////////////////
vector<pair<int, pll>> graf[200005];
map<pii, ll> dp; map<pii, bool> vis;
map<int, vector<pair<pii, ll>>> g[200005]; //g[v][c] -> v mtnum enq c ov durs enq galis c ov
int main() {
    fastio;
    ll n, m, x, y, c, p; cin >> n >> m;
    fri(m) {
        cin >> x >> y >> c >> p;
        graf[x].pb({y, {c, p}});
        graf[y].pb({x, {c, p}});
    }
    map<ll, ll> ma;
    frr(1, 1 + n) {
        for(auto it : graf[i])
            ma[it.ss.ff] += it.ss.ss;
        for(auto it : graf[i]) {
            g[i][0].pb({{it.ff, 0}, min(it.ss.ss, ma[it.ss.ff] - it.ss.ss)});
            g[i][0].pb({{it.ff, it.ss.ff}, 0});
            g[i][it.ss.ff].pb({{it.ff, 0}, ma[it.ss.ff] - it.ss.ss});
        }
        ma.clear();
    }
    for(ll i = 1; i <= n; i++) {
        for(auto it : graf[i])
            dp[{i, it.ss.ff}] = 1e18;
        dp[{i, 0}] = 1e18;
    }
    priority_queue<pair<ll, pll>> q;
    dp[{1, 0}] = 0;
    q.push({0, {1, 0}});
    while(!q.empty()){
        pii p = q.top().ss; q.pop();
        if(vis[p]) continue;
        vis[p] = 1;
        for(pair<pii, ll> u : g[p.ff][p.ss]) {
            if(!vis[u.ff] && dp[u.ff] > dp[p] + u.ss) {
                dp[u.ff] = dp[p] + u.ss;
                q.push({-dp[u.ff], u.ff});
            }
        }
    }
    // prll(dp);
    if(dp[{n, 0}] == 1e18) cout << -1;
    else cout << dp[{n,0}];
    return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14384 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 8 ms 14368 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 6 ms 14384 KB Output is correct
7 Correct 9 ms 14692 KB Output is correct
8 Correct 7 ms 14464 KB Output is correct
9 Correct 14 ms 15444 KB Output is correct
10 Correct 15 ms 15468 KB Output is correct
11 Correct 9 ms 15188 KB Output is correct
12 Correct 11 ms 15056 KB Output is correct
13 Correct 12 ms 15196 KB Output is correct
14 Correct 11 ms 15200 KB Output is correct
15 Correct 10 ms 15028 KB Output is correct
16 Correct 12 ms 15188 KB Output is correct
17 Correct 11 ms 15064 KB Output is correct
18 Correct 8 ms 14680 KB Output is correct
19 Correct 11 ms 15008 KB Output is correct
20 Correct 12 ms 15112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 50300 KB Output is correct
2 Correct 183 ms 32612 KB Output is correct
3 Correct 383 ms 53476 KB Output is correct
4 Correct 259 ms 39776 KB Output is correct
5 Correct 1435 ms 124136 KB Output is correct
6 Correct 1130 ms 112900 KB Output is correct
7 Correct 685 ms 93620 KB Output is correct
8 Correct 902 ms 95824 KB Output is correct
9 Correct 1101 ms 95924 KB Output is correct
10 Correct 571 ms 73752 KB Output is correct
11 Correct 139 ms 55596 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14384 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 8 ms 14368 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 6 ms 14384 KB Output is correct
7 Correct 9 ms 14692 KB Output is correct
8 Correct 7 ms 14464 KB Output is correct
9 Correct 14 ms 15444 KB Output is correct
10 Correct 15 ms 15468 KB Output is correct
11 Correct 9 ms 15188 KB Output is correct
12 Correct 11 ms 15056 KB Output is correct
13 Correct 12 ms 15196 KB Output is correct
14 Correct 11 ms 15200 KB Output is correct
15 Correct 10 ms 15028 KB Output is correct
16 Correct 12 ms 15188 KB Output is correct
17 Correct 11 ms 15064 KB Output is correct
18 Correct 8 ms 14680 KB Output is correct
19 Correct 11 ms 15008 KB Output is correct
20 Correct 12 ms 15112 KB Output is correct
21 Correct 403 ms 50300 KB Output is correct
22 Correct 183 ms 32612 KB Output is correct
23 Correct 383 ms 53476 KB Output is correct
24 Correct 259 ms 39776 KB Output is correct
25 Correct 1435 ms 124136 KB Output is correct
26 Correct 1130 ms 112900 KB Output is correct
27 Correct 685 ms 93620 KB Output is correct
28 Correct 902 ms 95824 KB Output is correct
29 Correct 1101 ms 95924 KB Output is correct
30 Correct 571 ms 73752 KB Output is correct
31 Correct 139 ms 55596 KB Output is correct
32 Correct 283 ms 48696 KB Output is correct
33 Correct 387 ms 51456 KB Output is correct
34 Correct 772 ms 79924 KB Output is correct
35 Correct 613 ms 67324 KB Output is correct
36 Correct 772 ms 81972 KB Output is correct
37 Correct 861 ms 90236 KB Output is correct
38 Correct 900 ms 103544 KB Output is correct
39 Correct 363 ms 61724 KB Output is correct
40 Correct 967 ms 101124 KB Output is correct
41 Correct 1111 ms 101260 KB Output is correct
42 Correct 964 ms 104600 KB Output is correct
43 Correct 318 ms 55576 KB Output is correct
44 Correct 628 ms 77088 KB Output is correct
45 Correct 884 ms 89496 KB Output is correct
46 Correct 645 ms 87196 KB Output is correct
47 Correct 842 ms 87232 KB Output is correct
48 Correct 1574 ms 129020 KB Output is correct