Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
WA5 Test | vtalgo23_Erbaev_336183 | 1160. Network | 22 апр 2023 14:15 | 1 |
WA5 Test vtalgo23_Erbaev_336183 22 апр 2023 14:15 So I was checking if the 2 vertices of the graph already connected, but didn't consider the test below and wasted a lot of time looking for a mistake and rewriting the code 4 3 1 2 1 3 4 2 2 3 3 Correct output: 3 3 1 2 3 4 2 3 My output: 2 2 1 2 3 4 |
Usefull test | Zombie1995 | 1160. Network | 23 фев 2023 18:55 | 1 |
For me this test was usefull: 7 11 1 2 7 1 4 5 2 4 9 2 3 8 2 5 7 3 5 5 4 5 15 4 6 6 5 6 8 5 7 9 6 7 11 |
Sample case incorrect? | guilty spark | 1160. Network | 10 сен 2020 23:57 | 2 |
It can be done with only 3 cables with max value of 1. Got AC “You are to help Andrew to find the way to connect hubs so that all above conditions are satisfied.” So you can output any correct answer. |
output format hint (wa1) | Olerinskiy | 1160. Network | 5 авг 2020 18:01 | 1 |
you should output edges in input order |
First Test | vtalgo20_GSavin | 1160. Network | 15 апр 2020 01:13 | 1 |
The first test is something like this 4 4 1 2 1 2 3 1 3 4 2 4 1 1 I hope this helps you |
INCREDIBLE easy problem. | Mahilewets | 1160. Network | 17 июл 2017 21:22 | 3 |
You can just sort edges in non-increasing order and add them sequentially until there are two or more connectivity components... It is absolutely of no importance How many edges are used Only the size if the largest edge matters I DON'T KNOW why the problem rating is not 80, but 300. Don't say things like There you need DSU Anansi's Cobweb requires DSU And it is only 170 rating points |
WA6 | SProf | 1160. Network | 11 янв 2017 01:38 | 2 |
WA6 SProf 16 фев 2016 17:19 i try to solve it with kruskal and it gives me wa6 can anyone help me? struct edge { int len; int a; int b; }; int rank[1024]; int parent[1024]; edge e[15008]; int n,m; int get_parent(int x) { if (x != parent[x])parent[x] = get_parent(parent[x]); return parent[x]; } bool join_dsu(int x, int y){ x = get_parent(x); y = get_parent(y); if (x == y) return false; if (rank[x] < rank[y]) parent[x] = y; else if (rank[x] > rank[y]) parent[y] = x; else parent[y] = x, ++rank[x]; return true; } // read edges // sort edges by len // p[i] = i, for i = 1..n // let l_min = 0; // i = 1..m // if ( join_dsu( e[i].a, e[i].b) ){ l_min = e[i].len; } // print l_min and all edges where len <= l_min, GOOD LUCK !! |
WA#5 | Grim_Disciple | 1160. Network | 3 фев 2016 06:59 | 2 |
WA#5 Grim_Disciple 2 окт 2009 18:23 need help. i used Kruskal's algorithm hi, you already solved this problem perhaps someone else might stuck in this test also: for Kruskal's algorithm i used to use this union method and got WA5, static void union(int su, int sv) { int segu = seg_in_hub[su]; seg_in_hub[sv] = segu; }//seg_in_hub[1..H+1] initialized with 1,2,3..H Instead, i rewrote this method and the solution got accepted static int union(int su, int sv) { int c = 1; int segu = seg_in_hub[su]; int segv = seg_in_hub[sv]; for (int i=0; i<seg_in_hub.length; i++) { if (seg_in_hub[i] == segu) { c++; seg_in_hub[i] = segv; } } return c; } //Also check if method returns H then break the loop |
Explanation what's the problem about | PrankMaN | 1160. Network | 4 апр 2013 22:04 | 1 |
|
usefull hint | Roman Rubanenko | 1160. Network | 1 дек 2011 22:55 | 3 |
Just minimize the max length of a single cable,then output all the edges that shorter then max or equal. GL yes but in example test 4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1 max is 1 and you must print 1 5 1 2 1 3 2 3 3 4 2 4 but answer is 1 4 1 2 1 3 2 3 3 4 There are multiple answers satisfy the condition. Both you wrote are correct. |
It Just a MST! | lshain | 1160. Network | 18 июл 2011 14:19 | 1 |
4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1 1 3 1 2 1 3 3 4 |
which MST algo do you prefer | tiancaihb | 1160. Network | 25 ноя 2010 21:14 | 6 |
I think, that this problem can be solved without MST. Just use binary search by maximum of single cable length and check accessibility of every node of graph. NlogM :) I like Kruskal's algo, as it is easy to implement it using disjoint set systems with O(n*logn) running time. |
2 Admin: problems with checker | Baurzhan | 1160. Network | 24 апр 2010 16:10 | 2 |
After wa1 many times i submit programms that should got CE (i print some strings,not numbers) but got wa1. Also i print nothing - again wa1,but not CE. It's very strange. May be checker to this problem is incorrect? |
wa1 | Baurzhan | 1160. Network | 24 апр 2010 02:24 | 1 |
wa1 Baurzhan 24 апр 2010 02:24 I submit prim's realization that got AC at olympiads.ru. Also i submitted kruskal's realization that got AC at some past contest. Why both AC programms can't pass test #1? can somebody give me tricky test cases? |
To Andmins!!! It is very surprising!!! | Виктор (marilyn_manson@bk.ru) | 1160. Network | 29 мар 2010 23:57 | 5 |
I wrote two idental programs in C++ and Pascal. First works for 0.565 sec, another for 0.062. I means, that tests for C++ and Pascal are different?! But why time is different??? If you used cin and cout ... I used cin/cout and still AC 0.046 |
MLE | KALO | 1160. Network | 18 фев 2010 15:07 | 1 |
MLE KALO 18 фев 2010 15:07 Why I got MLE#3? I'm using 1 int[M][3] matrix to store the edges, 3 short[N+1] arrays for Union-find, and an additional short[N] to store the resulting spanning tree. Bug in qsort. Edited by author 18.02.2010 15:19 |
MST ? | Roman Lipovsky | 1160. Network | 23 сен 2008 23:30 | 4 |
MST ? Roman Lipovsky 13 окт 2004 00:04 I think, that 1160 is MST problem. Is my idea correct? And explain me, please, is my output for sample input correct : 1 3 1 2 2 3 3 4 No, I's not MST. Read problem again. Re: MST ? GaLL [fac. of philology Tyumen SU] 18 янв 2007 22:42 It's MST, but with another metric. It's classic MST: all MST with minimum total weight are also ones with minimal weight of the maximal rib. Simple nonmodified Cruscal solve it by ~0.15 sec. |
Could anyone tell me why I get TLE #13 using disjoint sets? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1160. Network | 15 сен 2008 21:26 | 3 |
program ural1160; const maxn=1000; maxm=15000; type edge=record v1,v2:word;l:longint;end; var root:array[1..maxn]of word; e:array[1..maxm]of edge; n,m,i:word; procedure qsort(s,t:word); var p,i,j:word; te:edge; begin if s>=t then exit; p:=s+random(t-s+1); te:=e[p];e[p]:=e[s]; i:=s;j:=t; repeat while (i<j) and (e[j].l>=te.l) do dec(j); if i=j then break;e[i]:=e[j];inc(i); while (i<j) and (e[i].l<=te.l) do inc(i); if i=j then break;e[j]:=e[i];dec(j); until i=j; e[i]:=te; qsort(s,i-1); qsort(i+1,t); end; procedure pathcomp(x:word); var r,t:word; begin r:=x; while root[r]<>r do r:=root[r]; while root[x]<>r do begin t:=root[x];root[x]:=r;x:=t; end; end; begin read(n,m); for i:=1 to m do read(e[i].v1,e[i].v2,e[i].l); qsort(1,m); for i:=1 to n do root[i]:=i; for i:=1 to m do begin pathcomp(e[i].v1);pathcomp(e[i].v2); if root[e[i].v1]<>root[e[i].v2] then begin root[root[e[i].v1]]:=root[e[i].v2]; dec(n); end; if n=1 then break; end; writeln(e[i].l); writeln(i); for n:=1 to i do writeln(e[n].v1,' ',e[n].v2); end. Try to add {$M 64000000} in front. In fact you got crash(stack overflow) It's no use to add that. I've tried, but I failed. |
Why WA? | Andriy Kozachuk(VNTU) | 1160. Network | 22 июл 2008 16:19 | 1 |
Why WA? Andriy Kozachuk(VNTU) 22 июл 2008 16:19 Help me please. I can't find error this is my code: #include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; int main(){ int n,m; cin>>n>>m; int i; vector<pair<int,pair<int,int> > >a(m); vector<int>c(n); for(i=0;i<m;i++) cin>>a[i].second.first>>a[i].second.second>>a[i].first; for(i=0;i<n;i++) c[i]=i; sort(a.begin(),a.end()); int kil=n; int pot=0; while(kil>1){ if(c[a[pot].second.first]!=c[a[pot].second.second]){ int c2=c[a[pot].second.second]; int c1=c[a[pot].second.first]; for(i=0;i<n;i++) if(c[i]==c2) c[i]=c1; kil--; } pot++; } cout<<a[pot-1].first<<endl; cout<<pot<<endl; for(i=0;i<pot;i++) cout<<a[i].second.first<<' '<<a[i].second.second<<endl; return 0; } Edited by author 22.07.2008 16:20 |
What a Strange thing! | 198808xc | 1160. Network | 24 апр 2005 15:10 | 1 |
I forgot to change ma ARRAY board from 1 to 0, that is: Flag:array [1..MaxN] of Longint; TO Flag:array [0..MaxN] of Longint; First time, I got WA @ 9!!!!!! Then I got AC. It's strange, isn't it? They should have reminded me that I got CRASH, not WA. |