Show all threads Hide all threads Show all messages Hide all messages |
WA5 Test | vtalgo23_Erbaev_336183 | 1160. Network | 22 Apr 2023 14:15 | 1 |
WA5 Test vtalgo23_Erbaev_336183 22 Apr 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 Feb 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 Sep 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 Aug 2020 18:01 | 1 |
you should output edges in input order |
First Test | vtalgo20_GSavin | 1160. Network | 15 Apr 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 Jul 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 Jan 2017 01:38 | 2 |
WA6 SProf 16 Feb 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 Feb 2016 06:59 | 2 |
WA#5 Grim_Disciple 2 Oct 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 Apr 2013 22:04 | 1 |
|
usefull hint | Roman Rubanenko | 1160. Network | 1 Dec 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 Jul 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 Nov 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 Apr 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 Apr 2010 02:24 | 1 |
wa1 Baurzhan 24 Apr 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 Mar 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 Feb 2010 15:07 | 1 |
MLE KALO 18 Feb 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 Sep 2008 23:30 | 4 |
MST ? Roman Lipovsky 13 Oct 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 Jan 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 Sep 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 Jul 2008 16:19 | 1 |
Why WA? Andriy Kozachuk(VNTU) 22 Jul 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 Apr 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. |