oj.uz

Submission #718529

# Submission time Handle Problem Language Result Execution time Memory
718529 2023-04-04T09:33:42 Z vinnipuh01 Robot (JOI21_ho_t4) C++17
100 / 100
 614 ms 55572 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;


    freopen ( "sum.in", "r", stdin )
*/

struct Node {
	int dp, u;
};

vector <int> vv;

struct cmp {
	bool operator () ( const Node& a, const Node& b ) const {
		if ( a.dp == b.dp ) {
			return a.u < b.u;
		}
		return a.dp < b.dp;
	}
};

int n, m, x, y, z[ 200001 ], t[ 200001 ];
map <int, int> mp[ 100001 ], mpp[ 200001 ];
int dp[ 200001 ];
int dpp[ 200001 ];
vector <pair<int, int> > v[ 100001 ];
set <Node, cmp > st;


main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x >> y >> z[ i ] >> t[ i ];
		mp[ x ][ z[ i ] ] += t[ i ];
		mp[ y ][ z[ i ] ] += t[ i ];
		v[ x ].push_back( { y, i } );
		v[ y ].push_back( { x, i } );
		dpp[ i ] = oo;
	}
	for ( int i = 1; i <= n; i ++ )
		dp[ i ] = oo;
	dp[ 1 ] = 0;
	st.insert( { 0, 1 } );
	while ( st.size() ) {
		Node u = *st.begin();
		st.erase( st.begin() );
		for ( auto to : v[ u.u ] ) {
			dpp[ z[ to.second ] ] = min( dpp[ z[ to.second ] ], dp[ to.first ] );
		}
		for ( auto to : v[ u.u ] ) {
			if ( dp[ to.first ] > u.dp + t[ to.second ] ) {
				st.erase( { dp[ to.first ], to.first } );
				dp[ to.first ] = u.dp + t[ to.second ];
				st.insert( { dp[ to.first ], to.first } );
			}
			if ( dp[ to.first ] > u.dp + mp[ u.u ][ z[ to.second ] ] - t[ to.second ] ) {
				st.erase( { dp[ to.first ], to.first } );
				dp[ to.first ] = u.dp + mp[ u.u ][ z[ to.second ] ] - t[ to.second ];
				st.insert( { dp[ to.first ], to.first } );
			}
			if ( dp[ to.first ] > dpp[ z[ to.second ] ] + mp[ u.u ][ z[ to.second ] ] - t[ to.second ] ) {
				st.erase( { dp[ to.first ], to.first } );
				dp[ to.first ] = dpp[ z[ to.second ] ] + mp[ u.u ][ z[ to.second ] ] - t[ to.second ];
				st.insert( { dp[ to.first ], to.first } );
			}
		}
		for ( auto to : v[ u.u ] )
			dpp[ z[ to.second ] ] = oo;
	}
	mn = dp[ n ];
	if ( mn == oo )
		cout << "-1\n";
	else
		cout << mn << "\n";
}

Compilation message

Main.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main () {
      | ^~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 8 ms 16784 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 9 ms 16832 KB Output is correct
8 Correct 9 ms 16844 KB Output is correct
9 Correct 10 ms 17108 KB Output is correct
10 Correct 10 ms 17108 KB Output is correct
11 Correct 10 ms 16980 KB Output is correct
12 Correct 9 ms 16900 KB Output is correct
13 Correct 10 ms 17012 KB Output is correct
14 Correct 11 ms 17008 KB Output is correct
15 Correct 10 ms 16852 KB Output is correct
16 Correct 10 ms 16960 KB Output is correct
17 Correct 10 ms 16964 KB Output is correct
18 Correct 10 ms 16852 KB Output is correct
19 Correct 13 ms 17012 KB Output is correct
20 Correct 10 ms 16876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 27872 KB Output is correct
2 Correct 41 ms 22084 KB Output is correct
3 Correct 112 ms 30180 KB Output is correct
4 Correct 62 ms 24248 KB Output is correct
5 Correct 472 ms 50424 KB Output is correct
6 Correct 439 ms 50244 KB Output is correct
7 Correct 206 ms 48040 KB Output is correct
8 Correct 251 ms 43320 KB Output is correct
9 Correct 265 ms 43384 KB Output is correct
10 Correct 187 ms 37328 KB Output is correct
11 Correct 94 ms 31180 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 8 ms 16784 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 9 ms 16832 KB Output is correct
8 Correct 9 ms 16844 KB Output is correct
9 Correct 10 ms 17108 KB Output is correct
10 Correct 10 ms 17108 KB Output is correct
11 Correct 10 ms 16980 KB Output is correct
12 Correct 9 ms 16900 KB Output is correct
13 Correct 10 ms 17012 KB Output is correct
14 Correct 11 ms 17008 KB Output is correct
15 Correct 10 ms 16852 KB Output is correct
16 Correct 10 ms 16960 KB Output is correct
17 Correct 10 ms 16964 KB Output is correct
18 Correct 10 ms 16852 KB Output is correct
19 Correct 13 ms 17012 KB Output is correct
20 Correct 10 ms 16876 KB Output is correct
21 Correct 97 ms 27872 KB Output is correct
22 Correct 41 ms 22084 KB Output is correct
23 Correct 112 ms 30180 KB Output is correct
24 Correct 62 ms 24248 KB Output is correct
25 Correct 472 ms 50424 KB Output is correct
26 Correct 439 ms 50244 KB Output is correct
27 Correct 206 ms 48040 KB Output is correct
28 Correct 251 ms 43320 KB Output is correct
29 Correct 265 ms 43384 KB Output is correct
30 Correct 187 ms 37328 KB Output is correct
31 Correct 94 ms 31180 KB Output is correct
32 Correct 104 ms 31568 KB Output is correct
33 Correct 140 ms 30228 KB Output is correct
34 Correct 236 ms 39616 KB Output is correct
35 Correct 196 ms 34920 KB Output is correct
36 Correct 192 ms 37340 KB Output is correct
37 Correct 221 ms 41052 KB Output is correct
38 Correct 223 ms 47852 KB Output is correct
39 Correct 126 ms 36428 KB Output is correct
40 Correct 277 ms 44620 KB Output is correct
41 Correct 286 ms 44876 KB Output is correct
42 Correct 298 ms 47060 KB Output is correct
43 Correct 133 ms 31972 KB Output is correct
44 Correct 182 ms 41308 KB Output is correct
45 Correct 270 ms 38988 KB Output is correct
46 Correct 195 ms 38768 KB Output is correct
47 Correct 199 ms 41132 KB Output is correct
48 Correct 614 ms 55572 KB Output is correct