oj.uz

답안 #775642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775642 2023-07-06T16:50:40 Z Filya Robot (JOI21_ho_t4) C++14
100 / 100
 1493 ms 124416 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 (miak depqy vori depqum sovorakan dijiky sxal klini en a, vor nuyn guynov ham mtnenq ham durs ganq u dra costy menq avel gumarac linenq(ma[c] - p[c]))
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)}); //sovorakan kox
            g[i][0].pb({{it.ff, it.ss.ff}, 0}); //depi ed c es mi koxy chenq hashvi vortev c ic en myusy hashvum enq arden
            g[i][it.ss.ff].pb({{it.ff, 0}, ma[it.ss.ff] - it.ss.ss}); //mer gagatic ed costov urish gagat durs gal
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14408 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 12 ms 15436 KB Output is correct
10 Correct 12 ms 15444 KB Output is correct
11 Correct 10 ms 15208 KB Output is correct
12 Correct 10 ms 15060 KB Output is correct
13 Correct 11 ms 15188 KB Output is correct
14 Correct 11 ms 15188 KB Output is correct
15 Correct 10 ms 14932 KB Output is correct
16 Correct 12 ms 15248 KB Output is correct
17 Correct 11 ms 15064 KB Output is correct
18 Correct 7 ms 14676 KB Output is correct
19 Correct 10 ms 15060 KB Output is correct
20 Correct 11 ms 15060 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 50556 KB Output is correct
2 Correct 154 ms 32836 KB Output is correct
3 Correct 367 ms 53712 KB Output is correct
4 Correct 219 ms 40072 KB Output is correct
5 Correct 1472 ms 124416 KB Output is correct
6 Correct 1077 ms 113168 KB Output is correct
7 Correct 717 ms 93940 KB Output is correct
8 Correct 880 ms 96044 KB Output is correct
9 Correct 1052 ms 96124 KB Output is correct
10 Correct 561 ms 74100 KB Output is correct
11 Correct 125 ms 55952 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14408 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 12 ms 15436 KB Output is correct
10 Correct 12 ms 15444 KB Output is correct
11 Correct 10 ms 15208 KB Output is correct
12 Correct 10 ms 15060 KB Output is correct
13 Correct 11 ms 15188 KB Output is correct
14 Correct 11 ms 15188 KB Output is correct
15 Correct 10 ms 14932 KB Output is correct
16 Correct 12 ms 15248 KB Output is correct
17 Correct 11 ms 15064 KB Output is correct
18 Correct 7 ms 14676 KB Output is correct
19 Correct 10 ms 15060 KB Output is correct
20 Correct 11 ms 15060 KB Output is correct
21 Correct 386 ms 50556 KB Output is correct
22 Correct 154 ms 32836 KB Output is correct
23 Correct 367 ms 53712 KB Output is correct
24 Correct 219 ms 40072 KB Output is correct
25 Correct 1472 ms 124416 KB Output is correct
26 Correct 1077 ms 113168 KB Output is correct
27 Correct 717 ms 93940 KB Output is correct
28 Correct 880 ms 96044 KB Output is correct
29 Correct 1052 ms 96124 KB Output is correct
30 Correct 561 ms 74100 KB Output is correct
31 Correct 125 ms 55952 KB Output is correct
32 Correct 275 ms 45564 KB Output is correct
33 Correct 382 ms 49032 KB Output is correct
34 Correct 769 ms 76744 KB Output is correct
35 Correct 631 ms 64704 KB Output is correct
36 Correct 731 ms 79804 KB Output is correct
37 Correct 829 ms 87392 KB Output is correct
38 Correct 901 ms 100400 KB Output is correct
39 Correct 354 ms 57440 KB Output is correct
40 Correct 1033 ms 96164 KB Output is correct
41 Correct 1072 ms 96292 KB Output is correct
42 Correct 970 ms 100360 KB Output is correct
43 Correct 327 ms 53556 KB Output is correct
44 Correct 624 ms 72720 KB Output is correct
45 Correct 846 ms 85948 KB Output is correct
46 Correct 642 ms 84008 KB Output is correct
47 Correct 801 ms 84292 KB Output is correct
48 Correct 1493 ms 124288 KB Output is correct