В задаче сказано, проверить существует ли такая команда 'x' что она обыграет и команду A и команду В, если существует то ответ No иначе YES в таком случае можно использовать bitset I cant ivent any tests that my solution will fail, but I have WA1! Can any body help... Give me some test! Plz... example tests 4 0110 0011 0001 1000 4 1 4 2 3 3 2 4 1 my output: No No No No 3 010 000 100 3 1 3 3 1 2 3 out: No Yes No Is it correct? Give some more tests! You should print "YES", but not "Yes"... WA 2 CODE: program china; var t:char; i,j,k:integer; a:array[1..100,1..100] of boolean; b:array[1..100] of integer; chk:array[1..100] of boolean; x,y,q,n,m:integer; procedure solve(k:integer); var i:integer; begin for i:=1 to n do begin if a[k,i] then begin if not chk[i] then begin chk[i]:=true; solve(i); end; end; end; end; begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(t); if t='0' then a[i,j]:=false else a[i,j]:=true; end; readln; end; for i:=1 to n do begin fillchar(chk,n,false); solve(i); for j:=1 to n do begin if chk[j] then b[i]:=b[i]+1; end; end; readln(q); for i:=1 to q do begin readln(x,y); if b[x]>b[y] then writeln('YES') else writeln('No'); end; end. may be this test will help you: 4 0010 0001 0100 0000 4 1 2 1 4 4 1 4 3 answer: YES YES YES No Why answer for 1 4 and 4 1 YES and what is the anwer for 4 0100 0000 0001 0000 7 1 2 2 1 3 4 4 3 3 1 1 3 3 2 Why answer for 1 4 and 4 1 YES Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". My answer for your test: YES YES YES YES YES YES YES Thank you, your answer helped me mutch! Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". Where this is written in the statement? Why can't I solve the problem this way: 1. Make transitive closure of the given graph (matrix A)using Floyd. 2. For every request (pair i j) print "YES" if A[i][j] = 1 otherwise print "No". Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES". Where this is written in the statement? Here: "In this case we say that the team A is stronger than the teams B and C (more formally, A is stronger than B if A has beaten B or if A has beaten a team C which is stronger than B)." Edited by author 18.10.2006 23:11 Edited by author 18.10.2006 23:114 1 anwer is No, because 1 better than 3, 3 better than 2, 2 better than 4 => 1 better than 4 Really fast. for (int k = 0; k < n; ++k) { for (int i = graph[k]._Find_first(); i < n; i = graph[k]._Find_next(i)) { graph[k] |= graph[i]; } } What is the meaning of this problem ? Edited by author 11.09.2017 19:22 Edited by author 11.09.2017 19:22 My algo is O(N*N*sqrt(N)). Насколько я понял, есть орграф без циклов, при этом если из вершины v1 можно попасть в v2, из v2 в v3, то и из v1 можно попасть в v3 (дуга моделирует победу). Команда v1 лучше v2, если нет u, отличной от v1 и v2/ из u можно попасть в v1 и v2. Код с WA2: #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> const int nmax = 1005; bool a[nmax][nmax]; int d[nmax], p[nmax]; //d[v]=0,если нет входящих дуг в v, p[v]-вершина u/ v достижима из u и d[v]=0. bool used[nmax]; char ch; int n, q, v, u; void DFS(int v, int par); void main() { scanf("%d\n", &n); for (int i = 1; i <= n; i++) { d[i] = 0; used[i] = false; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%c", &ch); if (ch == '0') a[i][j] = 0; else a[i][j] = 1; d[j]+=a[i][j]; if (j == n) scanf("\n"); } } for (int i = 1; i <= n; i++) { if (d[i] == 0) { p[i] = i; DFS(i, i); } }
scanf("%d\n", &q); for (int i = 1; i <= q; i++) { scanf("%d %d\n", &v, &u); if ((d[v] > 0) && (d[u] > 0) && (p[v] == p[u])) printf("No\n"); else printf("YES\n"); } } void DFS(int v, int par) { used[v] = true; for (int i = 1; i <= n; i++) { if ((!used[i]) && (a[v][i] == 1)) { p[i] = par; DFS(i, par); } } } Ошибка была в том, что из несколько вершин, не имеющих входные дуги, можно попасть в некоторую вершину. Edited by author 03.01.2017 22:31 According to my program, test #5 contains cycles. Isn't it forbidden by the statement? почему возникает такая проблема? код вроде соответствует примеру, приведенному в руководстве. В Visual Studio 2010 все работает. что делать? NVM, got AC. Had BIG problems understanding the problem statement! Thanks to all who wrote their contemplations about it! Edited by author 08.03.2009 15:26 But i receive WA2. Problem is standart transative closer algorithm using DFS Interesting feater that in chaina football player may be stronger than himself because of circle. Let P(a)=list of Ancestors and GrandAncestors and .. of a; Then a,b-YES ~P(a)^P(b)=Empty P(a) would better have as bitset I have TLE 24 because forgotten reachabylity algorithm O(n) For our forum shold maintain standard algorithm Use library please! It seems that transative closure as a rule has o(n^3) therefore when n=1000 we have no chances. But by god help strong components can be calculated for linear time and we can use forest of strong components. No for players a and b if and only if a and be dosn't belong to the same tree in this fotest. So what about sample? 2 and 3 belong to the same tree, but answer is "No". I thought, answer is "No", only if a and b common parent and there is no way from a to b. Am i right? 1. DFS for all parent nodes 2. For each node store its parent in matrix [N][N/8] (bit mask) 3. For each A and B - if there is a common parent return "No" Excuse me!. I were mistaken. But I am shure that answer can be taken in terms of forest of strong components or Gerz graf. Let Sc(a)- number of component for a; NumT(i) - number of tree in the forest for comp i Ncomp[i]- amount of vertex in i-th comp Root[i]=1 if i- root in forest Then: 1) if (Sc(a)==Sc(b)) and (a!=b)) F(a,b)=No; 2) if NumT(Sc(a))==NumT(Sc(b)) and Root(Sc(a))==0 and Root(Sc(b))==0 F(a,b)=No; 3) if NumT(Sc(a))==NumT(Sc(b)) and Root(Sc(a))==1 and Ncomop(Sc(a)>1) F(a,b)=No; 4) if NumT(Sc(a))==NumT(Sc(b)) and Root(Sc(b))==1 and Ncomop(Sc(b)>1) F(a,b)=No; Otherwise F(a,b)=YES Algo for strong comps has O(|V|+|E|)=O(n^2) But I have WA4 If your don't agree with my arguments send message ,plese! I finished and have Ac (0.6) on my Idea. All is right but final refinement says that sftrong component i may belong to many trees and we must use SubT[1..Nco][1..NT] matrix instead of array SubT[1..Nco].I used my previous strong components program algo O(|V|+O(|E|) from Kormen where i used vector container for adjacent lists this is the reason of bad time of executing. This is interface of the program: void S_Comps(vector<short>smeg[MAX],short Nv,short &Nco,bool korn[MAX], short Scomps[MAX],char *Sm,short &NT,char *SubT,short Ncomp[MAX]) After O(n^3) Floid difficulties program has passed all tests immediately after removing silly mistakes. I doubt there are any strong components larger than 1 (otherwise words "stronger" and "beaten" in problem statement loose big part of their original meaning). Also, strong components form DAG, not necessarily a forest. My Floyd in O(N^3) got AC within 0.25 sec. 1. Is it true that there are no loops in the input data? 2. Is it true and A and B are always such that neiher A is sronger than B, nor B is stronger than A? Edited by author 10.07.2008 05:40 I use Floyd to obtain the transitive closure and got TLE at case #24... What is the answer for sample input and a query 2 1? Is it YES? Because there is no team C that is stronger then team 1, and that team 2 is weaker than team C. No one is answering, so I'll do it myself :-) Of course the answer is YES! My explenation is correct. |
|