QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#578629	#9260. Raiffeisenbank Logistics	AWR^#	ML	785ms	289200kb	C++20	2.0kb	2024-09-20 20:31:08	2024-09-20 20:31:09

Judging History

你现在查看的是最新测评结果

[2024-09-20 20:31:09]
评测

测评结果：ML
用时：785ms
内存：289200kb

查看

[2024-09-20 20:31:08]
提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

#define fir first
#define sec second
#define mpr make_pair

#define vv vector
#define eb emplace_back

#define Fr(i, l, r) for (ll i = l; i <= r; ++i)
#define Rf(i, r, l) for (ll i = r; i >= l; --i)

const long long INF = 1e18;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll T; cin >> T;
	while (T --> 0) {
		ll n, m; cin >> n >> m;
		using type = array<ll, 4>;
		vv<type> b;
		vv<vv<ll>> h(n + 2);
		vv<vv<ll>> id(n + 2);
		vv<ll> siz(n + 2);
		vv<map<ll, ll>> rk(n + 2);
		Fr (i, 1, m) {
			ll u, v, t;
			cin >> u >> v >> t;
			b.eb(type{u, v, 0, t});
			b.eb(type{v, u, 1, t});
			h[u].eb(t), h[v].eb(t);
		}
		ll cnt = 0;
		Fr (i, 1, n) {
			sort(h[i].begin(), h[i].end());
			h[i].erase(unique(h[i].begin(), h[i].end()), h[i].end());
			siz[i] = h[i].size() + 1, id[i].resize(siz[i] + 2);
			Fr (j, 1, siz[i] - 1) rk[i][h[i][j - 1]] = j, id[i][j] = ++cnt;
			id[i][siz[i]] = ++cnt;
		}
		// Fr (i, 1, n) cout << siz[i] << "\n";
		vv<vv<pll>> G(cnt + 2);
		Fr (i, 1, n) Fr (j, 1, siz[i] - 1) G[id[i][j]].eb(id[i][j + 1], 0);
		for (auto [u, v, w, t] : b) {
			ll t1 = rk[v][t];
			// if (t1 == siz[v]) continue;
			++t1;
			// cout << "u = " << u << ", v = " << v << "\n";
			// cout << rk[u][t] << ", " << t1 << "\n";
			// cout << id[u][rk[u][t]] << ", " << id[v][t1] << "\n";
			G[id[u][rk[u][t]]].eb(id[v][t1], w);
		}
		vv<ll> dis(cnt + 2, INF);
		dis[id[1][1]] = 0;
		ll stp = 0;
		vv<queue<ll>> q(n + 2);
		q[0].push(id[1][1]);
		while (stp < n) {
			while (!q[stp].empty()) {
				ll x = q[stp].front(); q[stp].pop();
				// cout << "x = " << x << ", stp = " << stp << "\n";
				if (stp > dis[x]) continue;
				for (auto [y, w] : G[x]) if (dis[y] > dis[x] + w) {
					dis[y] = dis[x] + w, q[dis[y]].push(y);
				}
			}
			++stp;
		}
		ll res = dis[id[n][siz[n]]];
		cout << (res == INF ? -1 : res) << "\n";
	}
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3548kb

input:

output:

result:

ok 1 number(s): "2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

output:

-1
1

result:

ok 2 number(s): "-1 1"

Test #3:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

8
2 1
1 2 1
2 1
2 1 1
2 1
1 1 1
2 1
2 2 1
2 1
1 2 1000000000
2 1
2 1 1000000000
2 1
1 1 1000000000
2 1
2 2 1000000000

output:

0
1
-1
-1
0
1
-1
-1

result:

ok 8 numbers

Test #4:

score: 0

Accepted

time: 0ms

memory: 3760kb

input:

1
2 1
1 2 1

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 5ms

memory: 3640kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
0
-1
1
-1
-1
-...

result:

ok 1000 numbers

Test #6:

score: 0

Accepted

time: 5ms

memory: 3648kb

input:

output:

-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
0
0
-1
-1
-1
-1
1
1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
0
-1
-1
1
0
0
1
-1
-1
-1
-1
1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #7:

score: 0

Accepted

time: 6ms

memory: 3560kb

input:

output:

0
1
-1
2
-1
-1
1
0
0
-1
1
-1
0
-1
1
-1
-1
-1
-1
1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
1
2
-1
1
-1
-1
2
1
-1
-1
-1
1
-1
1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
0
1
1
-1
1
-1
-1
1
2
-1
-1
1
-1
-1
0
-1
0
-1
0
-1
-1
-1
-1
1
-1
0
-1
0
-1
1
0
0
-1
-1
-1
-1
-1
1
1
-1
2
-1
-1
0
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
0
-1
1
-1
0
-1
0
-...

result:

ok 1000 numbers

Test #8:

score: 0

Accepted

time: 6ms

memory: 3564kb

input:

output:

2
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
2
-1
0
-1
-1
-1
-1
0
2
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
0
-1
0
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
2
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
...

result:

ok 1000 numbers

Test #9:

score: 0

Accepted

time: 6ms

memory: 3840kb

input:

output:

1
-1
-1
-1
0
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
2
0
0
-1
1
-1
-1
-1
0
-1
3
-1
-1
1
0
-1
-1
-1
-1
0
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
1
1
-1
-1
-1
1
0
-1
2
0
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
0
-1
...

result:

ok 1000 numbers

Test #10:

score: 0

Accepted

time: 6ms

memory: 3564kb

input:

1000
10 10
10 10 268155137
5 10 540061009
1 10 110627680
1 4 533692575
3 5 10438095
6 7 730490278
6 2 985939776
8 10 500039201
1 9 185735931
4 2 729538420
10 10
8 1 326383784
5 3 726281100
4 6 279162422
4 4 243297959
1 2 984988531
3 10 856724546
2 4 627158366
4 5 880246199
9 1 675003875
7 7 76366643...

output:

0
-1
-1
-1
-1
0
-1
2
1
-1
2
-1
-1
-1
-1
1
-1
1
-1
0
-1
2
1
2
-1
-1
0
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
0
-1
-1
-1
-1
-1
1
1
1
-1
0
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
0
-1
-1
-1
0
1
-1
2
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
0
-1...

result:

ok 1000 numbers

Test #11:

score: 0

Accepted

time: 7ms

memory: 3508kb

input:

output:

-1
1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
0
1
-1
0
-1
-1
-1
-1
0
0
1
1
-1
1
-1
-1
-1
0
-1
0
-1
-1
-1
1
-1
-1
1
-1
-1
1
0
-1
-1
0
0
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
-1
1
1
1
0
-1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
0
1
1
0
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
0
-1
0
...

result:

ok 1000 numbers

Test #12:

score: 0

Accepted

time: 9ms

memory: 3784kb

input:

output:

-1
-1
2
0
0
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
0
-1
-1
2
-1
-1
-1
-1
1
-1
0
0
1
1
1
1
1
0
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
1
-1
2
0
2
1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
0
1
-1
0
2
0
-1
0
-1
2
1
-1
0
-1
-1
2
-1
-1
-1
-1
2
-1
1
-1
-1
0
0
-1
0
0
2
-1
0
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
1
-1
1...

result:

ok 1000 numbers

Test #13:

score: 0

Accepted

time: 10ms

memory: 3824kb

input:

output:

-1
0
-1
0
0
-1
-1
-1
-1
-1
2
1
-1
-1
-1
-1
-1
0
-1
1
-1
-1
-1
0
-1
-1
-1
2
1
-1
-1
1
-1
-1
2
-1
0
1
1
-1
-1
-1
-1
-1
0
1
1
-1
-1
2
-1
-1
2
2
0
1
-1
0
-1
-1
0
1
-1
1
-1
0
-1
-1
0
1
2
0
0
-1
1
-1
1
0
-1
-1
-1
-1
0
0
-1
-1
0
2
1
0
1
-1
-1
2
1
1
0
0
2
2
1
1
-1
0
0
0
1
0
-1
1
-1
1
0
0
-1
-1
-1
-1
1
-1
-1...

result:

ok 1000 numbers

Test #14:

score: 0

Accepted

time: 12ms

memory: 3572kb

input:

output:

result:

ok 1000 numbers

Test #15:

score: 0

Accepted

time: 13ms

memory: 3640kb

input:

output:

result:

ok 1000 numbers

Test #16:

score: 0

Accepted

time: 14ms

memory: 3632kb

input:

1000
10 20
9 8 326353980
1 10 321178299
4 8 970616710
4 9 550923176
8 9 682488932
10 6 752852755
5 10 399703822
10 10 207683413
7 9 84451826
7 8 820433227
7 5 97884128
6 7 1405220
1 5 287655030
8 9 868446569
4 1 421832399
9 4 913601101
2 9 361785960
9 3 425625400
3 9 1891923
8 1 112588430
10 20
6 9 ...

output:

result:

ok 1000 numbers

Test #17:

score: 0

Accepted

time: 12ms

memory: 3580kb

input:

output:

result:

ok 1000 numbers

Test #18:

score: 0

Accepted

time: 15ms

memory: 3576kb

input:

output:

result:

ok 1000 numbers

Test #19:

score: 0

Accepted

time: 18ms

memory: 3596kb

input:

output:

result:

ok 1000 numbers

Test #20:

score: 0

Accepted

time: 25ms

memory: 3880kb

input:

output:

result:

ok 1000 numbers

Test #21:

score: 0

Accepted

time: 25ms

memory: 3544kb

input:

output:

result:

ok 1000 numbers

Test #22:

score: 0

Accepted

time: 26ms

memory: 3592kb

input:

1000
10 50
2 2 954153759
1 3 283444488
8 10 897162377
6 2 701352810
5 8 872948443
6 10 320895294
10 9 697730752
5 4 375661090
3 4 673334850
6 9 215515206
10 7 977251708
6 1 888046403
5 2 292147356
9 9 840382008
3 10 430429980
6 8 921004331
4 10 298467905
7 1 160104863
10 3 444341972
10 4 653051505
9...

output:

result:

ok 1000 numbers

Test #23:

score: 0

Accepted

time: 63ms

memory: 3900kb

input:

output:

result:

ok 1000 numbers

Test #24:

score: 0

Accepted

time: 78ms

memory: 3756kb

input:

output:

result:

ok 1000 numbers

Test #25:

score: 0

Accepted

time: 91ms

memory: 3976kb

input:

output:

result:

ok 1000 numbers

Test #26:

score: 0

Accepted

time: 130ms

memory: 3772kb

input:

output:

result:

ok 1000 numbers

Test #27:

score: 0

Accepted

time: 257ms

memory: 3856kb

input:

output:

result:

ok 1000 numbers

Test #28:

score: 0

Accepted

time: 312ms

memory: 3872kb

input:

1000
10 500
8 9 67526824
5 4 559064935
10 5 4911091
10 1 665435421
10 9 676899734
7 1 937378183
8 5 573246092
4 7 989380774
4 6 200810178
7 1 416005093
8 8 742684190
1 10 268750539
2 5 718281171
1 8 934536165
1 5 814664163
2 7 237449715
2 1 203051765
6 7 306356562
10 3 428234841
3 1 760994730
10 2 7...

output:

result:

ok 1000 numbers

Test #29:

score: 0

Accepted

time: 249ms

memory: 3856kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 1000 numbers

Test #30:

score: 0

Accepted

time: 258ms

memory: 3880kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #31:

score: 0

Accepted

time: 271ms

memory: 3920kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #32:

score: 0

Accepted

time: 287ms

memory: 4072kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 1000 numbers

Test #33:

score: 0

Accepted

time: 288ms

memory: 4016kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 1000 numbers

Test #34:

score: 0

Accepted

time: 510ms

memory: 54036kb

input:

5
10000 100000
16 3559 468695643
7133 1854 827377604
2253 8986 212718926
3378 8735 205907497
3784 3272 98819139
5961 1839 898392689
4722 371 109250145
8884 4871 589883888
7498 9813 70864069
9475 6017 175126069
2932 4557 863780576
7285 6064 122334857
5448 5260 360605203
2995 6162 705458859
9806 2832 ...

output:

result:

ok 5 number(s): "1 0 2 0 0"

Test #35:

score: 0

Accepted

time: 483ms

memory: 54304kb

input:

5
10000 100000
400 1662 499032381
6939 2059 486853387
8062 4311 263485029
6906 9144 898349721
1374 9791 287537913
1401 2514 179426639
3206 356 654913984
955 4491 102066327
3824 2238 428099250
5030 4171 796495242
3176 8123 228296196
1660 5633 794625946
4996 4363 891788658
4221 4267 717537153
5092 647...

output:

result:

ok 5 number(s): "1 0 2 1 1"

Test #36:

score: 0

Accepted

time: 497ms

memory: 53420kb

input:

5
10000 100000
9526 8284 30390295
2776 8832 185094918
939 7505 922941741
5631 7025 869203187
8618 8178 304297509
4573 6637 697002478
7831 8738 160865264
8640 1154 975091136
3872 1182 637499754
9369 8403 47264467
6368 2555 483838225
7177 4894 244976652
9845 1265 564379654
2955 1436 118973925
3645 199...

output:

result:

ok 5 number(s): "0 1 1 0 1"

Test #37:

score: 0

Accepted

time: 767ms

memory: 288656kb

input:

1
100000 500000
34635 46033 243840177
89991 69694 442882506
19968 21610 887963959
59100 4326 518891263
32030 66602 905457084
6365 4377 378500516
35716 52072 375354442
83763 63671 748057938
90167 71718 314322061
20985 57673 399305781
33422 9344 54429249
8621 10927 88073233
24414 18967 895092185
91512...

output:

-1

result:

ok 1 number(s): "-1"

Test #38:

score: 0

Accepted

time: 785ms

memory: 288568kb

input:

1
100000 500000
15188 94877 126956305
36064 18948 613736176
54124 38302 322768646
61948 64766 801195445
69649 93035 698032982
45412 52100 455948433
23657 16312 543752460
82338 71180 928014228
84388 81926 336635918
20855 4689 124954834
75713 19615 821948475
70517 69931 455049369
11652 49042 460926915...

output:

-1

result:

ok 1 number(s): "-1"

Test #39:

score: 0

Accepted

time: 774ms

memory: 289200kb

input:

1
100000 500000
52638 76426 305039729
14841 68201 344398357
20983 22290 197764822
54396 25205 378466923
96868 95277 340865776
25674 24014 678620542
87405 89065 712150478
24017 78689 548162006
45905 24838 63982479
20726 94809 705379695
85300 72989 734691893
73629 72040 116992802
66185 79117 26761645
...

output:

-1

result:

ok 1 number(s): "-1"

Test #40:

score: -100

Memory Limit Exceeded

input:

1
500000 500000
59280 54906 439822256
429265 418258 621212182
218147 211795 205467984
164946 71245 957403153
481375 344334 382889209
206719 295309 525844696
195710 220464 534488515
49094 402808 390137503
110467 267533 689219374
466476 328515 301654731
60840 13684 148387915
395867 144861 350257604
45...

output:

-1