Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | WA8 Please, explain, what is the reason? | Solverdce | 1320. Разбиение графа | 7 сен 2020 14:59 | 2 | WA8 Please, explain, what is the reason? Is this just a problem of input/output or this is just such test case? I found the problem, wrong algorithm. | This is a cool problem | Rabbit Girl ♥ | 1320. Разбиение графа | 18 май 2019 19:02 | 2 | So, we can decompose like this any connected graph G = (V, E), |E| = 2k, k in Z+? This is lovely, this is nice (I proved it using induction, I'm proud of myself, yay!). I came up to this idea, but failed to proof. | WA #5 | Faeton (Kyiv - Mohyla Academy) | 1320. Разбиение графа | 12 июл 2017 20:48 | 2 | WA #5 Faeton (Kyiv - Mohyla Academy) 4 мар 2008 21:59 | Implementation | competitivecoder | 1320. Разбиение графа | 28 апр 2017 02:55 | 2 | Posting code is not a nice idea. Moreover it is not ideal. | WA #14 | mezkresh | 1320. Разбиение графа | 28 апр 2017 02:53 | 2 | WA #14 mezkresh 28 мар 2016 18:24 In general this task is quite hard to make bugs if you know what to do... What is your approach? | My mistake was... | GastonFontenla | 1320. Разбиение графа | 5 авг 2015 05:29 | 1 | My mistake was usage of queue when the correct is using a stack. Only changed that, and then got AC 0.015 sec 480 KB. I'm so happy :D Edited by author 05.08.2015 05:31 | a simple test | Briana Banks | 1320. Разбиение графа | 4 авг 2014 10:42 | 2 | input 5 4 4 2 2 1 1 3 3 4 I think output should "1" but most of my colleagues' accepted programs print "0". Do I misunderstand the problem ? This is not valid input because the graph has to have an even number of edges. | Simple problem | Vladislav | 1320. Разбиение графа | 29 мар 2014 23:00 | 1 | It's very simple problem because all connected graphs which containes even number of edges can be divided into pairs of edges, which includes one common vertex!!!(and all connected graphs with odd number of edges can't be divided in such way) | WA#7,need help!!! | Oyh's 小号 | 1320. Разбиение графа | 4 фев 2014 18:11 | 3 | who can help me? I WA on #7.Why? here is my program: var a:array[1..1000]of longint; b:array[1..1000,1..1000]of boolean; n,i,j,x,y,m:longint; c:boolean; function find(x,y:longint):boolean; var i:longint; begin if b[x,y] then exit(false); for i:=1 to m do if (b[a[i],x])and(b[a[i],y])then begin b[x,y]:=true;b[y,x]:=true; exit(false); end; exit(true); end; begin while not seekeof do begin readln(x,y); b[x,x]:=true;b[y,y]:=true; b[x,y]:=true;b[y,x]:=true; c:=true; for j:=1 to m do if a[m]=x then begin c:=false;break;end; if c then begin inc(m);a[m]:=x; for i:=1 to m do if find(a[i],x) then begin writeln(0);halt; end; end; c:=true; for j:=1 to m do if a[m]=y then begin c:=false;break;end; if c then begin inc(m);a[m]:=y; for i:=1 to m do if find(a[i],y) then begin writeln(0);halt; end; end; end; writeln(1); end. Pls check for the following case: 5 6 5 8 5 9 6 7 8 9 9 10 Answer should be 1 Test 7 has invert vertexes. 10 1 1 2 asn: 1 I have many times WA, because my programm doesnt check it. | What is the test 1? | AlMag | 1320. Разбиение графа | 3 дек 2013 23:06 | 2 | Is test1 the sample? I have WA#1 !!! input 1 2 2 3 3 1 1 10 output 0 | EXCELLENT STATEMENT!!!!!!!!!!!!!!!!!!! | muhammad | 1320. Разбиение графа | 14 июн 2012 01:44 | 2 | CONGRATULATIONS TO THE AUTHOR!!!!! | Clarification (+) | Dmitry 'Diman_YES' Kovalioff | 1320. Разбиение графа | 5 сен 2010 08:51 | 9 | The text is incorrect: "...to present it by the set of pairs of adjacent edges..." means not to transform the graph into a form in which it will be unequivocally presented by the set of pairs of its adjacent edges (it is rather difficult problem), but only to share (divide, separate) it into pairs of adjacent edges (it is easy). i.g. you can divide graph [1-2-3-4-1] into [1-2] and [3-4] Text is correct. One can understand this problem with a help of simple example: Imagine graph drawn on a wall. Select any vertex and erase exactly two edges incidental to this vertex. The question of problem is: "Is it possible to erase all edges of graph doing in this way?". The text is "There is a simple graph with an even number of edges. You are to define if it is possible to present it by the set of pairs of adjacent edges (having a common vertex)." Isn't it? It differs from "Imagine graph drawn on a wall. Select any vertex and erase exactly two edges incidental to this vertex. The question of problem is: "Is it possible to erase all edges of graph doing in this way?"" Isn't it? I've understood the real definition, 'cause I was on quaterfinal, and I still think that the text doesn't correspond this definition. Text should be changed. It's easy. Isn't it? I think statement is correct. I also was at quarterfinal, but understand problem in right way. I was in jury of that quarterfinal, so I know this problem better. I doubt problem text will be changed, because union of original text and clarification text (about graph on a wall) should be enough to solve this (easy) problem. Too lazy to change or too stubborn to recognize a mistake? So now everyone who wants to solve this problem and was not in jury of that quarterfinal should get WA several times and then come to the board and see your "clarification"? By the way, do you know why this ("easy") problem has only 11% of AC? >Too lazy to change or too stubborn to recognize a mistake? Mostly: jury is very tired. There were no questions on this issue on contest, so text is OK.There are questions at timus - and they are answered. Anyway, before throwing such words ("lazy", "stubborn", "mistake") you should organize couple of quarterfinals (for example next quarterfinal) yourself. All question to jury of this particular contest should be posted to contest.ur.ru/board/ >By the way, do you know why this ("easy") problem has only 11% of AC? Here "easy" means "has simple solution" but not "is obvious". >Anyway, before throwing such words ("lazy", "stubborn", "mistake") you should organize couple of quarterfinals (for example next quarterfinal) yourself. Really? So I will take your word for it. I am ready to do it. In fact, I've thought about organizing 1/8 final zone, but I was not sure it is possible. And now such an opportunity! Thank you very much. Mail me to dimanyes@mail.ru for next discussing. To everyone: Mr. Mironenko wants me to organize next quaterfinal. So, welcome next year to Dmitry "Diman_YES" Kovalioff's Quaterfinal in Tyumen! Actually I didn't understand problem statement either. I don't like going to the boards before solving a problem because sometimes the solution is spoiled. In this particular case if you don't GUESS what the problem statement means you HAVE TO come to the board. | Who get AC in the way? | Rabidstorm | 1320. Разбиение графа | 31 мар 2010 19:52 | 2 | begin randomize; writeln(random(2)); end. Who can AC by this program??? =) if you are lucky enough | test ? | Nguyễn Cảnh Toàn | 1320. Разбиение графа | 4 янв 2009 15:41 | 2 | test ? Nguyễn Cảnh Toàn 4 янв 2009 08:26 1 2 2 3 3 1 1 10 in this test , i do not know why ? what about the others vertex ? 4,5,6,7,8,9 ?? "Imagine graph drawn on a wall. Select any vertex and erase exactly two edges incidental to this vertex. The question of problem is: "Is it possible to erase all edges of graph doing in this way?"" think again: 1 2 2 3 3 1 1 10 you will understand.... | how to input data in c / c ++? | lian lian | 1320. Разбиение графа | 4 янв 2009 08:23 | 3 | void Readinp() { int x,y; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); while (cin >> x >>y) { a[x][y]=1; a[y][x]=1; b[x]++; b[y]++; n=max(n,max(x,y)); } } | why? | lian lian (k421668239@gmail.com) | 1320. Разбиение графа | 17 дек 2008 03:02 | 1 | why? lian lian (k421668239@gmail.com) 17 дек 2008 03:02 Edited by author 25.12.2008 02:46 | Something wrong on testcase 6. | qwe | 1320. Разбиение графа | 13 сен 2008 01:26 | 23 | please check it. AC'ers try to submit your solution one more time. If its OK, then sorry(i'm stupid). First i got WA #6 I have counted the number of edges. in program is that code: If count=6 then while true do; TL#6 I changed to : If count=6 then begin writeln(1); halt; end; WA#6 Than: If count=6 then begib writeln(0); halt; end; WA#6... It's something strange, because output maybe only 1 or 0... No. I'm sure. Please submit your solution ad you'll see. I also get WA on test #6. Please tell me if you get AC. I also get WA on test #6. me too =( Edited by author 11.05.2004 23:50NO! Just submit your solution and you'll see i'm right! OK, but how... if count=6 then begin while true do; halt; end; TL; if count=6 then begin writeln(0); halt; end; WA if count=6 then begin writeln(1); halt; end; WA Is it possible? hm... accept... i just changed eof to seekoef. But why? Who can explain me? Thank you very much! I also got accepted just changing eof on seekeof. But what is the difference? Edited by author 13.05.2004 19:36 Edited by author 13.05.2004 19:37 There may be a following situation. A line break (eoln) ends the last line of input and your program read last number with "read" function, so only a number is removed from the input stream, but the eoln symbol is still in stream. At this moment "eof" function returns false (it sees eoln symbol, so it is not end of file), but "seekeof" returns true (it skips all whitespace in a stream including eoln symbol). #include <fstream> #include <stdio.h> using namespace std; int n, nm = 0; int arr[1010][1010] = {0}; int mark[1010] = {0}; int col[1010] = {0}; void dfs (int v) { mark[v] = nm; int i; for (i = 1; i <= n; ++i) { if (mark[i] == 0 && arr[v][i] == 1) { dfs (i); } } } int main () { //freopen ("a.in", "r", stdin); //freopen ("a.out", "w", stdout); int i, a, b; n = 0; while (scanf("%d%d", &a, &b) == 2) { arr[a][b] = 1; arr[b][a] = 1; if (a < b) { swap (a, b); } if (n < a) { n = a; } } for (i = 1; i <= n; ++i) { if (mark[i] == 0) { ++nm; dfs (i); } } for (i = 1; i <= n; ++i) { ++col[mark[i]]; } for (i = 1; i <= nm; ++i) { if (col[i] == 2) { printf ("0\n"); return 0; } } printf ("1\n"); return 0; } {$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O-,P+,Q-,R-,S-,T-,U-,V+,W-,X+,Y+,Z1} program z1320; {$APPTYPE CONSOLE} uses SysUtils; type pnode = ^tnode; tnode = record b:longint; next:pnode; end; var a:array [1..1000] of pnode; c:array [1..1000] of longint; b:array [1..1000] of boolean; n,m,i,j,k,t:longint; x:pnode; procedure init; begin reset(input,'input.txt'); rewrite(output,'output.txt'); end; procedure print; begin close(input); close(Output); halt(0); end; procedure swap(var a,b:longint); var t:longint; begin t:=a; a:=b; b:=t; end; procedure dfs(k:longint); begin b[k]:=true; inc(c[m]); while a[k]<>nil do begin if b[a[k]^.b]=false then dfs(a[k]^.b); a[k]:= a[k]^.next; end; end; begin init; n:=0; while not seekeof(input) do begin read(i,j); new(x); x^.b:=j; x^.next:=a[i]; a[i]:=x; new(x); x^.b:=i; x^.next:=a[j]; a[j]:=x; if i<j then swap(i,j); if i>n then n:=i; end; m:=0; for i:=1 to n do if b[i]=false then begin inc(m); dfs(i); end; for i:=1 to m do if c[i]=2 then begin write(0); halt(0); end; write(1); print; end. type int=integer; var n,i,j,col:int; g:array[1..1000,1..1000] of byte; vid:array[1..1000] of boolean; v:array[1..1000] of int; procedure dsd(curr,p:int); var j:int; begin for j:=1 to n do if (g[curr,v[j]]=1) and (not vid[v[j]]) and (j<>p) then begin inc(col); vid[v[j]]:=true; dsd(v[j],curr); end; end; begin n:=0; while not EOF do begin readln(i,j); g[i,j]:=1; g[j,i]:=1; if not vid[i] then begin inc(n);v[n]:=i;vid[i]:=true;end; if not vid[j] then begin inc(n);v[n]:=j;vid[j]:=true;end; end; fillchar(vid,sizeof(vid),false); for i:=1 to n do if not vid[v[i]] then begin col:=0; vid[v[i]]:=true; dsd(v[i],0); if col<2 then begin write(0);halt;end; end; write(1); end. | ufs | lian lian | 1320. Разбиение графа | 12 сен 2008 19:03 | 1 | ufs lian lian 12 сен 2008 19:03 | WA #20 | Ramzes2 (Cherkasy NU) | 1320. Разбиение графа | 5 авг 2008 18:27 | 2 | WA #20 Ramzes2 (Cherkasy NU) 5 авг 2008 18:16 I find mistake in my source code. I got AC | what function to use to determine the end of input in C++ ? | Grigor Gevorgian | 1320. Разбиение графа | 22 июн 2008 18:35 | 2 | in pascal it is 'seekeof()', and in C++ ? |
|
|