Общий форумUse BINARY SEARCH, AFTER THIS TEST I GOT AC I'M SO GLAD, I'M JUST IN SHOCK. I hope all my tests will help you, I find this task very useful for number theory if you have two progressions, one of which is with a very large step, then you can walk from the beginning of one progression to the beginning of the other if you have two progressions, one of which is with a very large step, then you can walk from the beginning of one progression to the beginning of the other This codes gives correct output in my system but submitting it shows Restricted Function. Plz help... ************************************** import Queue graph={} dic={} to_explore=Queue.Queue() def BFS(root): dic[root]=0 to_explore.put(root) while not to_explore.empty(): tmp=to_explore.get() for i in graph[tmp]: if i not in dic: dic[i]=dic[tmp]+1 to_explore.put(i) n=input() while n: s=raw_input().split() for i in s: if i not in graph: graph[i]=[] for j in s: if j!=i: if j not in graph[i]: graph[i].append(j) else: for j in s: if j!=i: if j not in graph[i]: graph[i].append(j) n-=1 if 'Isenbaev' in graph: BFS('Isenbaev') for i in graph: if i not in dic: dic[i]='undefined' for i in sorted(dic): print i,dic[i] else: for i in sorted(graph): print i,"undefined" Don`t the queue module starts with lowercase letter? Looks like: from queue(module) import Queue(function) Actually, I have pretty similar code and always have runtime error on the very first test Edited by author 20.08.2023 18:32 Edited by author 20.08.2023 18:32 The graph is not oriented graph. It makes solution easier. Edited by author 19.08.2023 12:29 Can be velocity lager than c? Try to think in terms of mathematics, trying to make accurate judgments This test helped me to find my bug. I modified dijkstra algo and added direction array. 9 12 7 3 9 3 9 2 1 2 1 3 4 7 4 1 5 1 4 8 5 8 6 5 2 6 1 8 Answer:0 Edited by author 31.01.2013 17:37 Thanks a lot! I was maintaining an array how[], which was storing how to get at that node (uphill mode or downhill node). But that failed Test case #11. I modified the code such that I start Dijkstra's algorithm at the destination node (Orlov's city) as the source node and Ivan's city as the target node. I actually interchanged source with end. So now I think my how[] array stores how one should get here. And it passed all test cases! Does this work because we have no limitation on how to start, but rather how we end makes more impact on the solution? I cannot derive a formal proof. Any comments are welcome You have to use 2d array to have 2 min costs from s to t with 2 states 0 (up) and 1 (down) (dis[u][0], dis[u][1]), if you just you 1d array and AC, it must be lucky. This is my AC code run in 0.031s: ((const) inf = 1e9, (define) ep = emplace (= push/insert), (define) eb = emplace_back (= push_back), ep and eb both are faster than push and push_back, emplace_front/emplace/emplace_back = push_front/(push/insert)/push_back but faster because it doesn't copy then moves value into array, it pushes directly into array)
#pragma GCC optimize( "Ofast" ) #pragma GCC target( "avx2", "sse4.2", "abm", "bmi", "bmi2", "fma", "mmx", "popcnt", "lzcnt" ) #include <bits/stdc++.h> #define endl '\n' #define inf 1e18 #define int long long #define pii pair <int, int> #define vii vector <pii> #define tiii tuple <int, int, int> #define viii vector <tiii> #define ep emplace #define eb emplace_back using namespace std; const int MaxN = 1e4 + 10; int n, m, s, t, f[MaxN][2]; vii a[MaxN]; priority_queue <tiii, viii, greater <tiii>> pq; signed main() { cin.tie(0) -> sync_with_stdio(0); __builtin_ia32_ldmxcsr ( 40896 );
fill(&f[0][0], &f[0][0] + sizeof(f) / sizeof(f[0][0]), inf);
cin >> n >> m; for (int u, v, i = 1; i <= m; ++i) { cin >> u >> v; a[u].eb(v, 0); a[v].eb(u, 1); } cin >> s >> t;
f[s][0] = f[s][1] = 0; pq.ep(f[s][0], s, 0); pq.ep(f[s][1], s, 1); while (!pq.empty()) { auto [x, u, y] = pq.top(); pq.pop(); if (x > f[u][y]) continue; if (u == t) break; for (auto [v, z] : a[u]) { int w = f[u][y] + (y != z); if (f[v][z] > w) pq.ep(f[v][z] = w, v, z); } }
cout << min(f[t][0], f[t][1]) << endl; } if you have any question, you can ask me :)) I'm native Russian language speaker, but I really cannot understand what is required in the problem: "Поскольку Вадим не любит сладкое, в конце он выберет себе самый маленький по площади кусочек, однако он не хочет, чтобы кто-то это заметил. Для этого современному обер-форшнейдеру нужно подобрать такой способ элегантно разделить торт, чтобы часть, которая достанется ему, была наибольшего размера." He doesn't like sweets, so he takes part of minimal size, but he wants to maximize size at the same time. WTF, where is the logic here, what does author want from us - to find maximin over all cuts, or something else? My program worked correctly on N in 1 to 9, and incorrectly on numbers greater than 9 (error in string concatenation). I kept getting an error on test 2 until I fixed the error. Apparently, in test 2, the input is a number greater than 10. Try this test: in: 11 out: ((((((((((sin(1)+11)sin(1-sin(2))+10)sin(1-sin(2+sin(3)))+9)sin(1-sin(2+sin(3-sin(4))))+8)sin(1-sin(2+sin(3-sin(4+sin(5)))))+7)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6))))))+6)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7)))))))+5)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8))))))))+4)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8+sin(9)))))))))+3)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8+sin(9-sin(10))))))))))+2)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8+sin(9-sin(10+sin(11)))))))))))+1 I made all my coordinate variables double, so I had a bug when I printed it out :( cout << (int)x << ' ' << int(y) << '\n'; -> fixed my bug I have tested, and 500 kbytes input reads about 20-30 ms in acm.timus.ru system. It equal to ~25 Mbytes/s speed read. Seems there installed HDD disk. There any plan to use fastest SSD disks in server side ? Many problems solutions actually took many times for accessing input/output, not calculating actual algorithm. 6 11 1 1 1 2 1 3 3 1 3 2 2 6 2 4 3 5 5 5 5 4 4 6 6 4 Answer: 0 Just prepare the equation as described and solve for c=x, display_sum + k - (entered_sum + x) == (n + 1) * 2; display_sum + k - entered_sum - x = 2 * n + 2; x = -2 * n - 2 + display_sum + k - entered_sum; if x < 0 then Big Bang! If you get WA5, check case, where policeman catch the thief until first tram arrive. |
|