Show all threads Hide all threads Show all messages Hide all messages | Can anybody explain? I was reciving WA3 but after revercing my output data I get AC. Why? | Виталий Черков | 1176. Hyperchannels | 15 Aug 2016 03:19 | 3 | Because the edges are directed Try this test 5 2 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 | No subject | Felix_Mate | 1176. Hyperchannels | 20 Dec 2015 00:48 | 1 | Edited by author 20.12.2015 17:14 | RUNTIME ERROR #12 ??? | chanfaiwtf | 1176. Hyperchannels | 11 Sep 2015 12:47 | 1 | i used Fleury algorithm to find a Euler cycle Edited by author 11.09.2015 12:47 | AC with Visual C++ 2010, yet TLE 14 with G++ 4.9?! | Kirill Nikonov | 1176. Hyperchannels | 6 Jan 2015 19:03 | 1 | Ridiculous! It's O(damn E)! AND I got rid of all the lists and used simple arrays instead. It just cannot get any faster than that... | Why this answer is not correct???? | Opportunity | 1176. Hyperchannels | 20 Jun 2013 13:11 | 1 | Input 4 2 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 Output 2 1 1 4 4 1 1 2 2 4 4 2 | TLE | IgorKoval(from Pskov) | 1176. Hyperchannels | 24 Mar 2012 00:22 | 1 | TLE IgorKoval(from Pskov) 24 Mar 2012 00:22 In C++ don't use cout and cin! Just use scanf(...) and printf(...). Enjoy! Edited by author 24.03.2012 00:22 | Is my algo correct? | Lebedev_Nicolay[Ivanovo SPU] | 1176. Hyperchannels | 22 Mar 2010 11:12 | 2 | Is my greedy algo correct? On each step I choose an edge to vertex with the greatest out-degree. I have WA 8. No (-) Erop [USU] 22 Mar 2010 11:12 Of course, you should find Euler cycle | Crash on 13 test | Olympic Bear (Nikolay Dubchuk) | 1176. Hyperchannels | 24 May 2008 17:33 | 1 | If you code on Java use Thread to kill stack overflow | AC and WA#3 | dimozzz | 1176. Hyperchannels | 18 Apr 2008 02:37 | 4 | This my AC program. If I change one cycle, I get WA#3. WHY???? import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { public static int[][] a; public static int[] d; public static int n; public static int top; public static int[] bol; public static void dfs(int v){ bol[v] = 1; int i; for(i = 0;i < n;i ++){ if(a[v][i] == 1){ a[v][i] = 0; dfs(i); } } d[top] = v; top ++; } public static void solve()throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); m --; a = new int[n][n]; d = new int[n * n + 1]; bol = new int[n]; top = 0; int i, j; int res = 0; for(i = 0;i < n;i ++){ st = new StringTokenizer(in.readLine()); for(j = 0;j < n;j ++){ a[i][j] = 1 - Integer.parseInt(st.nextToken()); if(i == j)a[i][i] = 0; res += a[i][j]; } } dfs(m); for(i = top - 1;i > 0;i --){ System.out.println((d[i] + 1) + " " + (d[i - 1] + 1)); } } public static void main(String[] args){ new Thread(){ public void run(){ try{ solve(); }catch(Exception e){ } } }.start(); } } This cycle. for(i = top - 1;i > 0;i --){ System.out.println((d[i] + 1) + " " + (d[i - 1] + 1)); } change to: for(i = 0;i < top - 1;i ++){ System.out.println((d[i] + 1) + " " + (d[i + 1] + 1)); } had the same problem. Test #3. Bad: for (int i=0; i<ResultSize-1; ++i) printf("%d %d\n", Result[i]+1, Result[i+1]+1); Good: int i=ResultSize; while (i-->1) printf("%d %d\n", Result[i]+1, Result[i-1]+1); Changed bad to good and got AC. Admins, please check test #3. There is such sentence in the problem statement: "One can pass through the channel only in one direction". That means the adjacency matrix is not symmetric and when you output the answer in reverse order, you may cross some channels such that channel (i,j) exists but (j,i) does not. you cannot post code here!!!!! | Crash on 2nd test | Neyrohirurg | 1176. Hyperchannels | 27 Mar 2007 00:01 | 1 | There was problem with this task, but now I get AC. Edited by author 27.03.2007 00:05 Edited by author 27.03.2007 00:36 | STACK OVERFLOW??? | RAVEman | 1176. Hyperchannels | 19 Mar 2007 19:06 | 2 | How can this algo get Stack overflow(test 12)? #include <string> #include <vector> #include<iostream> #include<queue> using namespace std; struct Pair{ int a,b; }; vector<int> res; int n,s; int a[1111][1111]; void dfs(int ver){ for(int i=0;i<n;i++) if(ver!=i && !a[ver][i]){ a[ver][i]=1; dfs(i); } res.push_back(ver); } int main(){ cin>>n>>s; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; dfs(s-1); reverse(res.begin(),res.end()); for(int i=1;i<res.size();i++) cout<<res[i-1]+1<<" "<<res[i]+1<<endl; system("pause"); return 0; } Use #pragma comment(linker, "/STACK:16777216") | hint's | ACM.Tolstobrov_Anatoliy[Ivanovo SPU] | 1176. Hyperchannels | 30 Sep 2006 13:29 | 2 | hint's ACM.Tolstobrov_Anatoliy[Ivanovo SPU] 8 Oct 2005 01:48 if you got Wa 2 try it 4 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 without output if you got MLE12 Not foget use dispose. Gool Luck and Have fun. another hint: if you have wa3, try to inverse output. for example, your program writes 3 1 1 2 2 3 try 3 2 2 1 1 3 GL | AC in 0. 3 sec and 773k! Although it isn't a very hard problem,it did difficult for pascal to got AC.I had got ML for more than 10 time... | Yu YuanMing | 1176. Hyperchannels | 29 Jun 2005 08:20 | 5 | why ? Dilyan 28 Jun 2005 23:43 why ? Edited by author 28.06.2005 23:43 I usually design algo according to the memory limit... Maybe I should rewrite the pro which needs less memory and faster... To Dilyan: Years ago, Pascal's memory will add another 370K, that is to say, your pro uses 641 + 370 > 1000k... That is why I said it is harder to got AC in pascal, I have to make exchange between time and space. Edited by author 29.06.2005 08:31 | Does the Eulerian cycle always exist? | Teragram | 1176. Hyperchannels | 2 Jun 2005 18:29 | 4 | I got WA on test 3. Here is my code: Program ex; Const Rule :Array [0..7] Of Integer =(1,2,4,8,16,32,64,128); Var G :Array [1..1001,0..125] Of Byte; Len,M :Integer; St,Ar :Array [1..32010] Of Integer; N,Be :Integer; Procedure Init; Var P,Q,U :Integer; Begin Readln(N,Be); For P:=1 To N Do For Q:=1 To N Do Begin Read(U); If (U=0) And (P<>Q) Then Inc(G[P,(Q-1) Div 8],Rule[(Q-1) Mod 8]); End; End; Procedure Main; Var I,J :Integer; Begin M:=0; Len:=1; St[1]:=Be; Repeat I:=St[Len]; J:=1; Repeat If G[I,(J-1) Div 8] And Rule[(J-1) Mod 8]>0 Then Break; Inc(J); Until J>N; If J<=N Then Begin Dec(G[I,(J-1) Div 8],Rule[(J-1) Mod 8]); Inc(Len); St[Len]:=J; End Else Begin Dec(Len); Inc(M); Ar[M]:=I; End; Until Len=0; If Ar[1]<>Be Then Begin Repeat Until False; End; For I:=1 To M-1 Do Writeln(Ar[I],' ',Ar[I+1]); End; Begin Init; Main; End. I can't find my mistake........ Who can give me some test........ This is my code : -------------------------------------------------------- const Maxn = 1010 ; var h : Array [0..Maxn,0..100] Of Integer ; l : Array [0..Maxn] Of Integer ; list : Array [0..66000] Of Integer ; len , n , first , x : LongInt ; procedure init ; var i , j , k : Integer ; begin read ( n , first ) ; for i := 1 to n do for j := 1 to n do begin read ( k ) ; if ( k = 0 ) and ( i <> j ) then begin Inc ( l[i] ) ; h[i,l[i]] := j ; end; end; end; procedure Dfs ( k : Integer ) ; begin While l[k] > 0 do begin Dec ( l[k] ) ; Dfs ( h[k,l[k]+1] ) ; end; Inc ( len ) ; list[len] := k ; end; procedure out ; var i : LongInt ; begin if n > 1 then begin write ( list[1] ) ; for i := 2 to len - 1 do begin writeln ( ' ' , list[i] ) ; write ( list[i] ) ; end; writeln ( ' ' , list[len] ) ; end; end; begin init ; Dfs ( first ) ; out ; end. Re: WA#3 Sergey Baskakov, Raphail and Denis 13 Mar 2005 10:02 I was getting WA3 until understood, that my program gives a wrong output on the following test: 3 2 0 0 1 1 0 0 0 1 0 To my mind, the only possible answer is as follows: 2 3 3 1 1 2 And my old solution output just the opposite, i.e. 2 1 1 3 3 2 Good luck (! rafailka. Edited by author 13.03.2005 10:02 | Question (+) | Roman Lipovsky | 1176. Hyperchannels | 13 Mar 2005 09:54 | 2 | For sample input: 4 2 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 I must find Eulerian cycle for such graph: 0 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 Is new graph correct or not? Edited by author 01.11.2004 21:34 What don't you like about it? I bet, it's OK(! rafailka. Edited by author 13.03.2005 09:56 | WA on #3, help please, MLE on #12 | Danica Porobic | 1176. Hyperchannels | 16 Jul 2004 19:55 | 3 | var g:array[1..1000,1..1000] of Boolean; i,j,n,a,k,s:smallint; procedure find(i:smallint); var j:smallint; begin for j:=n downto 1 do if g[i,j] then begin g[i,j]:=false; find(j) end; if s<>0 then writeln(s,' ',i); s:=i; end; begin assign(input,''); reset(input); readln(n,a); for i:=1 to n do for j:=1 to n do begin read(k); g[i,j]:=(k=0) and (i<>j) end; close(input); s:=0; find(a); end. If I put s in memory and write it in reverse order I get MLE on test 12: var g:array[1..1000,1..1000] of Boolean; i,j,n,a,k,st:smallint; s:array[1..32000] of smallint; procedure find(i:smallint); var j:smallint; begin for j:=n downto 1 do if g[i][j] then begin g[i][j]:=false; find(j) end; inc(st); s[st]:=i end; begin assign(input,''); reset(input); readln(n,a); for i:=1 to n do for j:=1 to n do begin read(k); g[i][j]:=(k=0) and (i<>j) end; close(input); st:=0; find(a); for i:=st-1 downto 1 do writeln(s[i+1],' ',s[i]); end. Please help me solve either of this two problems. There are two way to accept it: 1. Use stack instead of recursion. 2. Use recursion without variable "j". In all cases you can use array "st" and don't worry about memory limit. you can use dynamic lists for the graph instead of that bool matrix... | I got wa on test#3...Any trick??? | tbtbtb | 1176. Hyperchannels | 22 Apr 2004 19:08 | 8 | no tricks, just an Eulerian cycle on the negative edges... on the negative edges? Are there any differences with on the unnegative edags? you have the adjacency(?) matrix. Negative means that you change 1 with 0 and 0 with 1. Then, on this new graph you make an Eulerian cycle. I can post my source if really need I'm sorry I can't understand you. What does "change 1 with 0 and 0 with 1." mean? The problem gives you that binary matrix with a[i][j] = 1 if i and j are connected. Reversing 1 with 0 and vice-versa means that if i and j are connected than you unconnect them (i.e. a[i][j] = 0) and if they are not connected, a[i][j] = 0, you connect them, a[i][j] = 1. You do this because the spaceship can build cannals that don't exist, so it must walk only between unconnected nodes. Covering all cannals that do not exist and return to the initial node is a cycle that covers all these unconnected edges once, exactly like an Eulerian cycle. How did you pass the first tests if you didn't understand these? With all respect. Thank you! I mistook you at that time...Very sorry.. But I think I use the same method as you..Maybe there is something wrong with my code. | I always get WA. Can someone give me a test? This is my program. | Metal King | 1176. Hyperchannels | 20 Mar 2003 23:47 | 1 | #include <stdio.h> #include <stdlib.h> #define N 1050 #define setbit1(x,y) ( a[x][y >> 3] |= (1 << (y & 7)) ) #define setbit0(x,y) ( a[x][y >> 3] &= ~(1 << (y & 7)) ) #define getbit(x,y) ( a[x][y >> 3] & (1 << (y & 7)) ) int n, s, x, lev; int a[N][N/8], d[32010]; void read () { int i, j, v, x = 0; //freopen( "1176.in", "rt", stdin ); scanf( "%d%d", &n, &s ); for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) { scanf( "%d", &v ); if ( !v && i != j ) setbit1( i, j ), x++; } if ( !x ) exit( 0 ); } void ciclu (int s) { int j; lev++; for ( j = 1; j <= n; j++ ) if ( getbit( s, j ) ) { setbit0( s, j ); ciclu( j ); } d[++d[0]] = s; /* if ( !x || lev == 1 ) printf( "%d ", s ); else printf( "%d\n%d ", s, s ); x = s; lev--;*/ } int main () { int i;
read(); ciclu( s ); for ( i = 1; i < d[0]; i++ ) printf( "%d %d\n", d[i], d[i + 1] ); return 0; } | Simple DY-algo gets AC within 1 sec. :) (-) | Dmitry 'Diman_YES' Kovalioff | 1176. Hyperchannels | 28 Feb 2003 10:07 | 4 | What is it DY-algo?:) May be you have some links about it? | What is incorrect in this program???Please give me a test on which it fails | King Without Kingdom | 1176. Hyperchannels | 22 Jul 2002 02:46 | 1 | #include<iostream.h> int*conn[1001]; int*done[1001]; int quan[1001]; void razrul(int); int *tstr; void main(){ int str[1001]; tstr=new int[32200]; int i,j,n,q,a; cin >> n >> a; a--; for(i=0;i<n;i++) { for(j=0;j<n;j++) cin >> str[j]; q=0; str[i]=1; for(j=0;j<n;j++) if(str[j]==0) q++; if(q!=0) { conn[i]=new int[q]; done[i]=new int[q]; } quan[i]=0; for(j=0;j<n;j++) if(str[j]==0) { conn[i][quan[i]]=j; done[i][quan[i]]=0; quan[i]++; } } razrul(a); } void razrul(int a){ tstr[0]=a; int *tstr1; int ptstr=1,a0=a,i; while(1) { for(i=0;i<quan[a];i++) if(done[a][i]==0) { done[a][i]=1; a=conn[a][i]; tstr[ptstr]=a; ptstr++; break; } if(a==a0) break; } if(ptstr!=1) tstr1=new int[ptstr]; else return ; for(i=0;i<ptstr;i++) tstr1[i]=tstr[i]; for(i=0;i<ptstr-1;i++) { cout <<tstr1[i]+1<<" "<<tstr1[i+1]+1<<"\n"; razrul(tstr1[i+1]); } } |
|
|