# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
429052 | 2021-06-15T17:00:55 Z | amunduzbaev | Two Transportations (JOI19_transportations) | C++14 | 1165 ms | 58192 KB |
#include "Azer.h" #include "bits/stdc++.h" using namespace std; namespace{ //~ #include <ext/pb_ds/assoc_container.hpp> //~ #include <ext/pb_ds/tree_policy.hpp> //~ using namespace __gnu_pbds; //~ template<class T> using oset = tree<T, //~ null_type, less_equal<T>, rb_tree_tag, //~ tree_order_statistics_node_update>; #define ff first #define ss second #define pb push_back #define mp make_pair #define ub upper_bound #define lb lower_bound #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(),x.rend() #define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define vv vector #define mem(arr, v) memset(arr, v, sizeof arr) //~ #define int long long #define degub(x) cout<<#x<<" : "<<x<<"\n" #define GG cout<<"here"<<endl; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef vector<int> vii; typedef vector<pii> vpii; template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; } template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; } template<int sz> using tut = array<int, sz>; //~ void usaco(string s) { freopen((s+".in").c_str(),"r",stdin); //~ freopen((s+".out").c_str(),"w",stdout); NeedForSpeed } const int N = 2e5+5; const int mod = 1e9+7; const ll inf = 1e18; const ld Pi = acos(-1); #define MULTI 0 int n, m, k, s, t, q, ans, a; //, a[N]; int d[N], ligtest, rec, u, w, used[N]; vpii edges[N]; void upd(int u){ used[u] = 1; for(auto x : edges[u]) umin(d[x.ff], d[u] + x.ss); } void send(){ u = -1, w = mod + 1; for(int i=1;i<=n;i++){ if(used[i]) continue; if(d[i] < w) u = i, w = d[u]; } if(u == -1) return; //~ cout<<"A\n"; //~ for(int i=1;i<=n;i++) cout<<d[i]<<" "; //~ cout<<"\n"; w -= ligtest; umin(w, (1 << 9) - 1); //~ cout<<ligtest<<" "<<w<<"\n"; for(int i=8;~i;i--) SendA(w>>i&1); rec = 1; } int cost, len; } void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) { n = N, a = A; for(int i=0;i<a;i++){ int a = U[i] + 1, b = V[i] + 1, c = C[i]; edges[a].pb({b, c}), edges[b].pb({a, c}); } for(int i=1;i<=n;i++) d[i] = mod; d[1] = 0; upd(1), send(); } void ReceiveA(bool x) { cost = (cost << 1) | x; len++; if(rec == 1){ if(len == 9){ if(w <= cost){ for(int i=10;~i;i--) SendA(u>>i&1); ligtest += w; upd(u), send(), len = 0, cost = 0; } else rec = 2, ligtest += cost, len = 0, cost = 0; } } else if(rec == 2) { if(len == 11){ d[cost] = ligtest; upd(cost), send(), len = 0, cost = 0; } } } vector<int> Answer() { vii res; for(int i=1;i<=n;i++) res.pb(d[i]); return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 487 ms | 10124 KB | Output is correct |
2 | Correct | 9 ms | 9876 KB | Output is correct |
3 | Correct | 844 ms | 10164 KB | Output is correct |
4 | Correct | 841 ms | 19412 KB | Output is correct |
5 | Correct | 38 ms | 10112 KB | Output is correct |
6 | Correct | 785 ms | 11548 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9860 KB | Output is correct |
2 | Correct | 822 ms | 10180 KB | Output is correct |
3 | Correct | 639 ms | 10224 KB | Output is correct |
4 | Correct | 1162 ms | 36932 KB | Output is correct |
5 | Correct | 813 ms | 33384 KB | Output is correct |
6 | Correct | 89 ms | 10040 KB | Output is correct |
7 | Correct | 1165 ms | 33720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 694 ms | 10144 KB | Output is correct |
2 | Correct | 10 ms | 9876 KB | Output is correct |
3 | Correct | 556 ms | 10120 KB | Output is correct |
4 | Correct | 613 ms | 10132 KB | Output is correct |
5 | Correct | 711 ms | 10184 KB | Output is correct |
6 | Correct | 683 ms | 10124 KB | Output is correct |
7 | Correct | 625 ms | 10140 KB | Output is correct |
8 | Correct | 604 ms | 10124 KB | Output is correct |
9 | Correct | 488 ms | 10124 KB | Output is correct |
10 | Correct | 538 ms | 10048 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 351 ms | 10040 KB | Output is correct |
2 | Correct | 263 ms | 10032 KB | Output is correct |
3 | Correct | 341 ms | 22600 KB | Output is correct |
4 | Correct | 186 ms | 10132 KB | Output is correct |
5 | Correct | 500 ms | 19284 KB | Output is correct |
6 | Correct | 337 ms | 10080 KB | Output is correct |
7 | Correct | 288 ms | 10140 KB | Output is correct |
8 | Correct | 405 ms | 10092 KB | Output is correct |
9 | Correct | 483 ms | 27392 KB | Output is correct |
10 | Correct | 405 ms | 27520 KB | Output is correct |
11 | Correct | 598 ms | 44956 KB | Output is correct |
12 | Correct | 514 ms | 39968 KB | Output is correct |
13 | Correct | 344 ms | 10140 KB | Output is correct |
14 | Correct | 8 ms | 9856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 351 ms | 10040 KB | Output is correct |
2 | Correct | 263 ms | 10032 KB | Output is correct |
3 | Correct | 341 ms | 22600 KB | Output is correct |
4 | Correct | 186 ms | 10132 KB | Output is correct |
5 | Correct | 500 ms | 19284 KB | Output is correct |
6 | Correct | 337 ms | 10080 KB | Output is correct |
7 | Correct | 288 ms | 10140 KB | Output is correct |
8 | Correct | 405 ms | 10092 KB | Output is correct |
9 | Correct | 483 ms | 27392 KB | Output is correct |
10 | Correct | 405 ms | 27520 KB | Output is correct |
11 | Correct | 598 ms | 44956 KB | Output is correct |
12 | Correct | 514 ms | 39968 KB | Output is correct |
13 | Correct | 344 ms | 10140 KB | Output is correct |
14 | Correct | 8 ms | 9856 KB | Output is correct |
15 | Correct | 427 ms | 10052 KB | Output is correct |
16 | Correct | 368 ms | 10056 KB | Output is correct |
17 | Correct | 326 ms | 10088 KB | Output is correct |
18 | Correct | 470 ms | 19536 KB | Output is correct |
19 | Correct | 359 ms | 10112 KB | Output is correct |
20 | Correct | 563 ms | 19584 KB | Output is correct |
21 | Correct | 300 ms | 10120 KB | Output is correct |
22 | Correct | 358 ms | 10148 KB | Output is correct |
23 | Correct | 661 ms | 31452 KB | Output is correct |
24 | Correct | 683 ms | 31468 KB | Output is correct |
25 | Correct | 771 ms | 52940 KB | Output is correct |
26 | Correct | 774 ms | 45704 KB | Output is correct |
27 | Correct | 413 ms | 10192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 351 ms | 10040 KB | Output is correct |
2 | Correct | 263 ms | 10032 KB | Output is correct |
3 | Correct | 341 ms | 22600 KB | Output is correct |
4 | Correct | 186 ms | 10132 KB | Output is correct |
5 | Correct | 500 ms | 19284 KB | Output is correct |
6 | Correct | 337 ms | 10080 KB | Output is correct |
7 | Correct | 288 ms | 10140 KB | Output is correct |
8 | Correct | 405 ms | 10092 KB | Output is correct |
9 | Correct | 483 ms | 27392 KB | Output is correct |
10 | Correct | 405 ms | 27520 KB | Output is correct |
11 | Correct | 598 ms | 44956 KB | Output is correct |
12 | Correct | 514 ms | 39968 KB | Output is correct |
13 | Correct | 344 ms | 10140 KB | Output is correct |
14 | Correct | 8 ms | 9856 KB | Output is correct |
15 | Correct | 427 ms | 10052 KB | Output is correct |
16 | Correct | 368 ms | 10056 KB | Output is correct |
17 | Correct | 326 ms | 10088 KB | Output is correct |
18 | Correct | 470 ms | 19536 KB | Output is correct |
19 | Correct | 359 ms | 10112 KB | Output is correct |
20 | Correct | 563 ms | 19584 KB | Output is correct |
21 | Correct | 300 ms | 10120 KB | Output is correct |
22 | Correct | 358 ms | 10148 KB | Output is correct |
23 | Correct | 661 ms | 31452 KB | Output is correct |
24 | Correct | 683 ms | 31468 KB | Output is correct |
25 | Correct | 771 ms | 52940 KB | Output is correct |
26 | Correct | 774 ms | 45704 KB | Output is correct |
27 | Correct | 413 ms | 10192 KB | Output is correct |
28 | Correct | 597 ms | 10040 KB | Output is correct |
29 | Correct | 438 ms | 10044 KB | Output is correct |
30 | Correct | 679 ms | 33388 KB | Output is correct |
31 | Correct | 624 ms | 10076 KB | Output is correct |
32 | Correct | 595 ms | 30408 KB | Output is correct |
33 | Correct | 538 ms | 10128 KB | Output is correct |
34 | Correct | 536 ms | 10148 KB | Output is correct |
35 | Correct | 431 ms | 10152 KB | Output is correct |
36 | Correct | 443 ms | 34124 KB | Output is correct |
37 | Correct | 726 ms | 34148 KB | Output is correct |
38 | Correct | 741 ms | 58192 KB | Output is correct |
39 | Correct | 714 ms | 53580 KB | Output is correct |
40 | Correct | 554 ms | 10112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 487 ms | 10124 KB | Output is correct |
2 | Correct | 9 ms | 9876 KB | Output is correct |
3 | Correct | 844 ms | 10164 KB | Output is correct |
4 | Correct | 841 ms | 19412 KB | Output is correct |
5 | Correct | 38 ms | 10112 KB | Output is correct |
6 | Correct | 785 ms | 11548 KB | Output is correct |
7 | Correct | 9 ms | 9860 KB | Output is correct |
8 | Correct | 822 ms | 10180 KB | Output is correct |
9 | Correct | 639 ms | 10224 KB | Output is correct |
10 | Correct | 1162 ms | 36932 KB | Output is correct |
11 | Correct | 813 ms | 33384 KB | Output is correct |
12 | Correct | 89 ms | 10040 KB | Output is correct |
13 | Correct | 1165 ms | 33720 KB | Output is correct |
14 | Correct | 694 ms | 10144 KB | Output is correct |
15 | Correct | 10 ms | 9876 KB | Output is correct |
16 | Correct | 556 ms | 10120 KB | Output is correct |
17 | Correct | 613 ms | 10132 KB | Output is correct |
18 | Correct | 711 ms | 10184 KB | Output is correct |
19 | Correct | 683 ms | 10124 KB | Output is correct |
20 | Correct | 625 ms | 10140 KB | Output is correct |
21 | Correct | 604 ms | 10124 KB | Output is correct |
22 | Correct | 488 ms | 10124 KB | Output is correct |
23 | Correct | 538 ms | 10048 KB | Output is correct |
24 | Correct | 351 ms | 10040 KB | Output is correct |
25 | Correct | 263 ms | 10032 KB | Output is correct |
26 | Correct | 341 ms | 22600 KB | Output is correct |
27 | Correct | 186 ms | 10132 KB | Output is correct |
28 | Correct | 500 ms | 19284 KB | Output is correct |
29 | Correct | 337 ms | 10080 KB | Output is correct |
30 | Correct | 288 ms | 10140 KB | Output is correct |
31 | Correct | 405 ms | 10092 KB | Output is correct |
32 | Correct | 483 ms | 27392 KB | Output is correct |
33 | Correct | 405 ms | 27520 KB | Output is correct |
34 | Correct | 598 ms | 44956 KB | Output is correct |
35 | Correct | 514 ms | 39968 KB | Output is correct |
36 | Correct | 344 ms | 10140 KB | Output is correct |
37 | Correct | 8 ms | 9856 KB | Output is correct |
38 | Correct | 427 ms | 10052 KB | Output is correct |
39 | Correct | 368 ms | 10056 KB | Output is correct |
40 | Correct | 326 ms | 10088 KB | Output is correct |
41 | Correct | 470 ms | 19536 KB | Output is correct |
42 | Correct | 359 ms | 10112 KB | Output is correct |
43 | Correct | 563 ms | 19584 KB | Output is correct |
44 | Correct | 300 ms | 10120 KB | Output is correct |
45 | Correct | 358 ms | 10148 KB | Output is correct |
46 | Correct | 661 ms | 31452 KB | Output is correct |
47 | Correct | 683 ms | 31468 KB | Output is correct |
48 | Correct | 771 ms | 52940 KB | Output is correct |
49 | Correct | 774 ms | 45704 KB | Output is correct |
50 | Correct | 413 ms | 10192 KB | Output is correct |
51 | Correct | 597 ms | 10040 KB | Output is correct |
52 | Correct | 438 ms | 10044 KB | Output is correct |
53 | Correct | 679 ms | 33388 KB | Output is correct |
54 | Correct | 624 ms | 10076 KB | Output is correct |
55 | Correct | 595 ms | 30408 KB | Output is correct |
56 | Correct | 538 ms | 10128 KB | Output is correct |
57 | Correct | 536 ms | 10148 KB | Output is correct |
58 | Correct | 431 ms | 10152 KB | Output is correct |
59 | Correct | 443 ms | 34124 KB | Output is correct |
60 | Correct | 726 ms | 34148 KB | Output is correct |
61 | Correct | 741 ms | 58192 KB | Output is correct |
62 | Correct | 714 ms | 53580 KB | Output is correct |
63 | Correct | 554 ms | 10112 KB | Output is correct |
64 | Correct | 663 ms | 10220 KB | Output is correct |
65 | Correct | 820 ms | 35812 KB | Output is correct |
66 | Correct | 732 ms | 32672 KB | Output is correct |
67 | Correct | 687 ms | 10308 KB | Output is correct |
68 | Correct | 764 ms | 10212 KB | Output is correct |
69 | Correct | 1027 ms | 56920 KB | Output is correct |
70 | Correct | 867 ms | 48832 KB | Output is correct |
71 | Correct | 752 ms | 14244 KB | Output is correct |
72 | Correct | 623 ms | 10408 KB | Output is correct |