oj.uz

Submission #445865

# Submission time Handle Problem Language Result Execution time Memory
445865 2021-07-20T01:15:29 Z maomao90 Robot (JOI21_ho_t4) C++17
100 / 100
 1421 ms 180272 KB 
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 500005

int n, m;
unordered_map<int, vii> tadj[MAXN];
unordered_map<int, ll> sum[MAXN];
vector<pll> adj[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
ll d[MAXN];

map<ii, int> id;
int ptr;
inline int getid(ii a) {
	if (id.find(a) == id.end()) {
		id[a] = ptr++;
	}
	return id[a];
}

int main() {
	scanf("%d%d", &n, &m);
	REP (i, 0, m) {
		int a, b, c, p; scanf("%d%d%d%d", &a, &b, &c, &p);
		tadj[a][c].pb(MP(b, p));
		tadj[b][c].pb(MP(a, p));
		sum[a][c] += p;
		sum[b][c] += p;
	}
	ptr = n + 1;
	REP (u, 1, n + 1) {
		for (auto [c, vt] : tadj[u]) {
			for (auto [v, w] : vt) {
				adj[u].pb(MP(v, w));
				adj[u].pb(MP(v, sum[u][c] - w));
				adj[u].pb(MP(getid(MP(v, c)), 0));
				adj[getid(MP(u, c))].pb(MP(v, sum[u][c] - w));
			}
		}
	}
	REP (i, 1, ptr) {
		d[i] = LINF;
		debug("%d:", i);
		for (auto [v, w] : adj[i]) {
			debug(" (%d %d)", v, w);
		}
		debug("\n");
	}
	d[1] = 0;
	pq.push(MP(d[1], 1));
	while (!pq.empty()) {
		auto [ud, u] = pq.top(); pq.pop();
		if (ud != d[u]) continue;
		for (auto [v, w] : adj[u]) {
			if (mnto(d[v], d[u] + w)) {
				pq.push(MP(d[v], v));
			}
		}
	}
	if (d[n] == LINF) {
		printf("-1\n");
	} else {
		printf("%lld\n", d[n]);
	}
	return 0;
}

/*
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:81:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   81 |   for (auto [v, w] : adj[i]) {
      |             ^~~~~~
Main.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:61:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   int a, b, c, p; scanf("%d%d%d%d", &a, &b, &c, &p);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 66764 KB Output is correct
2 Correct 40 ms 66828 KB Output is correct
3 Correct 40 ms 66760 KB Output is correct
4 Correct 41 ms 66724 KB Output is correct
5 Correct 39 ms 66884 KB Output is correct
6 Correct 41 ms 66844 KB Output is correct
7 Correct 43 ms 67200 KB Output is correct
8 Correct 41 ms 66884 KB Output is correct
9 Correct 48 ms 67908 KB Output is correct
10 Correct 45 ms 67884 KB Output is correct
11 Correct 44 ms 67568 KB Output is correct
12 Correct 42 ms 67556 KB Output is correct
13 Correct 44 ms 67660 KB Output is correct
14 Correct 43 ms 67644 KB Output is correct
15 Correct 43 ms 67352 KB Output is correct
16 Correct 46 ms 67688 KB Output is correct
17 Correct 44 ms 67520 KB Output is correct
18 Correct 42 ms 67296 KB Output is correct
19 Correct 43 ms 67380 KB Output is correct
20 Correct 44 ms 67520 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 101572 KB Output is correct
2 Correct 197 ms 85312 KB Output is correct
3 Correct 446 ms 105724 KB Output is correct
4 Correct 258 ms 92260 KB Output is correct
5 Correct 1391 ms 180272 KB Output is correct
6 Correct 1112 ms 168040 KB Output is correct
7 Correct 657 ms 148480 KB Output is correct
8 Correct 937 ms 149284 KB Output is correct
9 Correct 983 ms 149340 KB Output is correct
10 Correct 722 ms 127520 KB Output is correct
11 Correct 472 ms 117580 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 66764 KB Output is correct
2 Correct 40 ms 66828 KB Output is correct
3 Correct 40 ms 66760 KB Output is correct
4 Correct 41 ms 66724 KB Output is correct
5 Correct 39 ms 66884 KB Output is correct
6 Correct 41 ms 66844 KB Output is correct
7 Correct 43 ms 67200 KB Output is correct
8 Correct 41 ms 66884 KB Output is correct
9 Correct 48 ms 67908 KB Output is correct
10 Correct 45 ms 67884 KB Output is correct
11 Correct 44 ms 67568 KB Output is correct
12 Correct 42 ms 67556 KB Output is correct
13 Correct 44 ms 67660 KB Output is correct
14 Correct 43 ms 67644 KB Output is correct
15 Correct 43 ms 67352 KB Output is correct
16 Correct 46 ms 67688 KB Output is correct
17 Correct 44 ms 67520 KB Output is correct
18 Correct 42 ms 67296 KB Output is correct
19 Correct 43 ms 67380 KB Output is correct
20 Correct 44 ms 67520 KB Output is correct
21 Correct 403 ms 101572 KB Output is correct
22 Correct 197 ms 85312 KB Output is correct
23 Correct 446 ms 105724 KB Output is correct
24 Correct 258 ms 92260 KB Output is correct
25 Correct 1391 ms 180272 KB Output is correct
26 Correct 1112 ms 168040 KB Output is correct
27 Correct 657 ms 148480 KB Output is correct
28 Correct 937 ms 149284 KB Output is correct
29 Correct 983 ms 149340 KB Output is correct
30 Correct 722 ms 127520 KB Output is correct
31 Correct 472 ms 117580 KB Output is correct
32 Correct 300 ms 100708 KB Output is correct
33 Correct 368 ms 101816 KB Output is correct
34 Correct 770 ms 126132 KB Output is correct
35 Correct 584 ms 115776 KB Output is correct
36 Correct 600 ms 133284 KB Output is correct
37 Correct 703 ms 139684 KB Output is correct
38 Correct 645 ms 153404 KB Output is correct
39 Correct 356 ms 109504 KB Output is correct
40 Correct 981 ms 149172 KB Output is correct
41 Correct 1006 ms 149292 KB Output is correct
42 Correct 1077 ms 153496 KB Output is correct
43 Correct 464 ms 106472 KB Output is correct
44 Correct 731 ms 121876 KB Output is correct
45 Correct 811 ms 138384 KB Output is correct
46 Correct 714 ms 139044 KB Output is correct
47 Correct 673 ms 137212 KB Output is correct
48 Correct 1421 ms 179920 KB Output is correct