Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | If you have TL 5 | ivanovmp | 1934. Чёрная метка | 3 сен 2022 00:05 | 2 | I had TL 5 because I did not add vertices to the BFS queue properly (sometimes I put the same vertex multiple times and then process in many times). You may try this test: [test cut, too big] Edited by moderator 06.09.2022 03:04 Answer is: 5 0.3836 1 12223 2 75002 3 | [Hint] If you got WA 4 | hadooken | 1934. Чёрная метка | 10 дек 2019 13:26 | 1 | Check that you are dealing with an undirected graph! | [Hint] If you got WA 2 | hadooken | 1934. Чёрная метка | 10 дек 2019 13:21 | 1 | You need to minimize number of visited islands firstly. Test: 3 3 1 3 1 3 99 1 2 0 2 3 0 Answer: 2 0.99 1 3 | I got stuck in test 4, any idea? | phantomape | 1934. Чёрная метка | 31 авг 2018 11:26 | 1 | #include <iostream> #include <vector> #include <cstring> #include <queue> using namespace std; int N, M, S, T, A, B, P; int total = 0; struct Edge { int to, next; double prob; } edges[100010]; int head[100010]; int parent[100010], dist[100010]; double prob[100010]; void addEdge(int start, int end, int p) { edges[total].to = end; edges[total].next = head[start]; edges[total].prob = 1.0 - (double)p / 100.0; head[start] = total++; } // The most tricky part is the probability, we are looking for the probability // of meeting Kraken in any route so it should be P(A|B), which equals to // P(A) + P(B) - P(AB) int main() { memset(head, -1, sizeof head); memset(parent, -1, sizeof parent); memset(dist, -1, sizeof dist); cin >> N >> M >> S >> T; for (int i = 0; i <= N; i ++) prob[i] = 0.0; for (int i = 1; i <= M; i ++) { cin >> A >> B >> P; addEdge(A, B, P); addEdge(B, A, P); } queue<int> q; q.push(S); dist[S] = 0 ; prob[S] = 1.0; while (!q.empty()) { int u = q.front(); q.pop(); for (int idx = head[u]; idx != -1; idx = edges[idx].next) { int v = edges[idx].to; double p = edges[idx].prob; if (dist[v] == -1 || (dist[v] == dist[u] + 1 && prob[v] < prob[u] * p)) { if (dist[v] == -1) { q.push(v); } dist[v] = dist[u] + 1; prob[v] = prob[u] * p; parent[v] = u; } } } vector<int> path; for (int i = T; i != S; i = parent[i]) { path.push_back(i); } path.push_back(S); cout << path.size() << " "; printf("%.7f\n", 1.0 - prob[T]); for (int i = path.size() - 1; i >= 1; i --) cout << path[i] << " "; cout << path[0] << endl; return 0; } | For C++ users getting TLE | pakhandi | 1934. Чёрная метка | 10 ноя 2015 13:27 | 1 | Use list to make the adjacency list and not vector. | TLE on STL vector | laishao_yuan | 1934. Чёрная метка | 6 сен 2015 08:19 | 1 | | TLE | Viktor | 1934. Чёрная метка | 1 сен 2015 07:26 | 4 | TLE Viktor 17 дек 2012 20:19 Don't use cin/cout or Scanner in java. Re: TLE Andrew Sboev [USU] 17 дек 2012 23:02 Seriously? 10^5, it's so few! Only cin, only hardcore! You shoudn't use cin/cout in every problem, in which n is big enough(n > 1000, for example) Edited by author 17.12.2012 23:02 cin/cout is not TLE, as long as you do cin.sync_with_stdio(false); Re: TLE jacketinsysu 1 сен 2015 07:26 Yes, you may think that the number of edge can be as large as n * (n - 1) / 2, which is O(n^2), where n is the number of vertex of the graph. (10^5)^2 = 10^10. is a rather large scale data for 1 second. | I'm getting WA on TEST 2 can anybody give a test plz???! | kerpoo | 1934. Чёрная метка | 15 авг 2015 23:35 | 3 | used dijkstra and update the probability (distance in normal dijkstra) of node v for v like below: dis[father[v]]=dis[father[v]] + edge(father[v],v).value - dis[father[v]]*edge(father[v],v).value is there any problem?! I'm not good enough in probability theory... Edited by author 15.08.2015 22:01 dijkstra doesn't do the job the problem asks for the <<shortest path>> even if it isn't the minimum of all ( but of course it should be minimal among all shortest path) tnx! I wasn't so careful in reading the problem! | To admins: weak tests (?) | MVM | 1934. Чёрная метка | 25 июл 2014 00:36 | 1 | Both my AC submissions answer wrong (locally) on test, which is generated by following code: int n = (int)1e5; printf("%d %d\n", n, n); printf("1 %d\n", n); printf("1 2 97\n"); printf("1 3 98\n"); for (int i = 2; i <= n - 2; i++) printf("%d %d %d\n", i, i + 2, 99); printf("%d %d 98\n", n - 1, n); To be exact, they answer 50001 1.0000000 1 2 ... n-2 n On the other side, answer is obviously path 1 3 ... n-1 n, because probability to not meet Kraken is (4 / 100^(n/2)) for it and (3 / 100^(n / 2)) for path 1, 2, ... By the way, it is far from the worst test. Actually, any test like this (with two diverging paths of same length), but where difference between products of (1 - probability of meeting Kraken) on edges of paths is 1 and these products are big is going to be much, much worse. P. S. If I am misunderstanding something (for example, 10^(-6) error is allowed for answer, not only for output (though even if it is true, it is not clear from Russian problem statement)), then I am very sorry. P. P. S. In hindsight it looks like statement is a bit unclear, but tests are OK (it looks like checker does allow any path with probability to meet Kraken not more than 10^(-6) + lowest probability), but formally, it is said in statement that path should be optimal, just answer can be written with some error). If it is so, I apologize for "wrong call", but I still would like to see some tweaks to statement. Edited by author 30.07.2014 04:29 | test 4 WA | Opportunity | 1934. Чёрная метка | 4 июн 2013 13:41 | 2 | who can give some tests like test 4, pls. test 4 is first big test n>90000. And another hint with probability. Calculate p[s]=1-p[s]/100. and p[t]=1-p[t]/100. and use the simple algo BFS . Try to calculate the best probability by formula p[qu->nod]=p[min] * qu->cost; where qu->nod the current node, and qu->cost the probability of this node. Dont forget that the answer is 1.-p[t]. The time of this algo is not good - 0,359, but it is very simple. Good luck!! P.S.qu->cost the same as p[s] and p[t] must be recalculate at the begining like this fscanf(in, "%d %d %d", &x, &y, &z); a[x]=new graf(y,1.-z/100.,a[x]); Sorry for my english!! Edited by author 04.06.2013 13:48 | how to get a 0.19 in the first test ? | uu_Innk | 1934. Чёрная метка | 5 янв 2013 22:01 | 4 | how to get a 0.19 in the first test ? what formula ? |
|
|