The 2nd test on the site does not pass, everything works for me, what should I do? try this test: input: 1 2 0 0 output: NO because for this sentences in the problem: "exactly one child has confessed the he (or she) had broken the cup". I dont notice to this and get WA#2. sorry for my poor english. GOOD LUCK! Edited by author 15.11.2010 23:48 I have a test on the website, no, what should I do? Here are jokes with statuses, such as we go in order along the vertices and if we get to a vertex that we haven't been to, then we start going in a cycle from this vertex, setting the status of this cycle, if we get to the same status, then this is a cycle, if we get to a vertex with a lower status, then everything is fine and we stop the cycle, and if the vertex has no status, then we just opened a new vertex and it turns out that the algorithm is linear I think this is very easy for 319 points of hardness, you only need to find cycle in directed graph Hardness is calculated automatically. Admins have nothing to do with it Why did you got wa on test 3 ? I'm having the same problem... :( try this test: 1 16 2 3 4 5 1 2 3 4 5 2 2 2 2 2 2 0 answer, it is clear, NO, but this test helped me when I had WA#3 I had WA#3, too. That test helped me. 1 5 0 0 0 0 0 It's NO, of course! ) Edited by author 16.03.2006 16:39 Edited by author 16.03.2006 16:40 Or maybe it is 1 5 0 3 4 5 3 Answer: NO >>Or maybe it is >> >>1 >>5 >>0 3 4 5 3 >> >>Answer: NO ASK, thank you. If there is a loop in graph that can be entered by branch from nodes earlier in list then loop nodes than some naive algorithms can fail on this test. By the way, why not to add the tag GRAPH THEORY to this problem? It not that deep though. Was wrong. Sorry Edited by author 26.01.2017 16:13 var g:array[1..25000,1..25000] of integer; v,i,j,n,f,un,uk,t,k,s,x:longint; Q:array[1..100000] of integer; p:array[1..25000] of integer; begin assign(input,'input.txt'); assign(output,'output.txt'); reset(input);rewrite(output); readln(t); for i:=1 to t do begin readln(n);k:=0; fillchar(g,sizeof(g),0); for j:=1 to n do begin read(s); if s=0 then begin f:=j; k:=k+1;g[j,j]:=0;end else begin g[j,s]:=1;g[s,j]:=1;end; if k>1 then break; end; readln; if k<>1 then begin Writeln('NO');end else begin for j:=1 to n do p[j]:=-1; fillchar(Q,sizeof(Q),0); un:=1; uk:=2; Q[1]:=f; p[f]:=0; x:=0; while un<>uk do begin v:=Q[un]; un:=un+1; for j:=1 to n do if (g[v,j]<>0) and (p[j]=-1) then begin Q[uk]:=j; uk:=uk+1; p[j]:=p[v]+1; end; end; for j:=1 to n do if p[j]=-1 then begin x:=1;break;end; if x=0 then writeln('YES') else writeln('NO'); end; end; end. #include <iostream> using namespace std; bool Chekcker(int A[],int k) { int i,j,v; bool circle=true; for(j=1;j<=k;j++) for(v=1;v<=k;v++) { if(A[v]==0 && A[j]==v ) A[j]=0; }
for(j=1;j<=k;j++) for(v=1;v<=k;v++) { if(A[j]==0 && A[v]==j ) A[v]=0; } for(v=1;v<=k;v++) if(A[v]==0) { circle=true;} else{circle=false;break;} return circle; } int main() { int n; cin>>n; int i,j,k = 0,v; int temK; bool circle; int conf; int A[30000]; for(i=1;i<=n;i++) { cin>>k; j=1; v=1; temK=k; circle=true; conf=0;
for(j=1;j<=k;j++) { cin>>A[j];
}
for(j=1;j<=k;j++) { if(A[j]==0) conf++; }
circle=Chekcker(A,k);
if(conf==0 || conf>1) {circle=false;}
if(circle==true) cout<<"YES"<<endl; else cout<<"NO"<<endl;
for(v=1;v<=k;v++) A[v]=0; }
return 0; } this code get correct on every test in the forum, however fails test #3. Whats Wrong???? I've sent the same solution using c++ and ruby - and ruby's version works 8 times slower than c++ solution and hardly passes TL (however all solutions were accepted, working time 0,125 vs 0,984 sec). I hope it might be caused by the old interpreter's version - can we use any newer version? This is the fragment of my program: scanf("%d", &n); for (int i = 0; i < n; i++) { int p; scanf("%d", &p); p--; if (p >= n) throw; If I remove throw, I'll have WA 3. So children can say absolutely incorrect information? No, all tests are correct. There is some bug in your code, it is reason of WA/RT 3 16 25000 0 3 4 5 ... 1 25000 0 3 4 5 ... 1 .... .... 25000 0 3 4 5 ... 1 Edited by author 21.11.2013 02:11 My AC program works on this test for 15 seconds.. 1 2 0 2 Is answer of second child to himself means "circle" ? This test is incorrect. If a child says that he is innocent then mother write down number 0 for his answer. So test could look as follows: 1 2 0 0 Certainly, answer is NO Test: 1 1 1 And what is the answer if yes? Answer is NO. 1 1 1 test is impossible if a[i]=i then a[i]:=0 because "Mummy has written down at ith position of the line the number of a child that the ith child pointed to, or 0 if the ith child suddenly confessed." so 1 1 0 and answer is YES Hope this test can help you: 2 3 2 1 0 1 0 - NO YES Good luck! var t,n,i,j:longint; d:array[1..25000] of integer; ok:boolean; begin read(t); for i:=1 to t do begin read(n);ok:=false; for j:=1 to n do begin read(d[j]); if d[j]=0 then ok:=true; end; if not ok then writeln('NO') else begin for j:=1 to n do if d[j]<>0 then if d[d[j]]=j then begin ok:=false;writeln('NO');break;end; if ok then writeln('YES'); end; end; end. var t,n,i,j,k:longint; d:array[1..25000] of integer; p:array[0..3124] of set of 0..7; ok:boolean; begin read(t); for i:=1 to t do begin read(n);ok:=false; for j:=1 to n do begin read(d[j]); if d[j]=0 then ok:=true; end; if not ok then writeln('NO') else begin fillchar(p,sizeof(p),0); for j:=1 to n do if (d[j]<>0)and not ((j-1) mod 8 in p[(j-1) div 8]) then begin p[(j-1) div 8]:=p[(j-1) div 8]+[(j-1) mod 8];k:=j; repeat k:=d[k]; if (k-1) in p[(k-1) div 8] then begin writeln('NO');ok:=false;break;end; p[(k-1) div 8]:=p[(k-1) div 8]+[(k-1) mod 8]; until d[k]=0; fillchar(p,sizeof(p),0); if not ok then break; end; if ok then writeln('YES'); end; end; end. "if d[j]=0 then ok:=true;" "...надо записать «YES» если показания детей, по крайней мере, выглядят непротиворечивыми: РОВНО ОДИН ребёнок признался в том, что он разбил кружку..." Can anybody help me with this problem, I nave WA3. Give me please some tests, I have WA3. So... Good problem! But I can't understand, who is this mother-heroine, which have 25000 children! =) By the way, they are must eat anything. Can you imagine house, where they are must living? I can't... ;) Interesting, author thought about this facts? =) It's perhaps the author's dream to have that many children - thus increasing the probability that at least one of them would have a higher IQ than himself. |
|