Show all threads Hide all threads Show all messages Hide all messages 
To admins: there is an error in test cases  ivzh  1280. Topological Sorting  13 May 2020 22:45  1 
Hi! Could you please check the next test case: ``` 3 2 1 2 1 3 3 1 2 ``` result should be `no`, but 4 my case i have `yes`. Despite this i had AC. Thanks in advance! Edited by author 13.05.2020 22:47 Edited by author 13.05.2020 22:47 
Wrong Answer on Test #16  Shabab Karim  1280. Topological Sorting  14 Sep 2019 01:26  4 
What is Test #16? Please someone help! What is Test #16? Please someone help! Same here... got stuck in Test16 . so why did you get the WA16? Well maybe someone gonna read this but i got WA #16 cause my logic was wrong. i thought that i need to check if i studied any of prerequisite BUT i must check if i studied ALL OF them. maybe my code would help idk #include <iostream> #include <vector> using namespace std; int N, M, a[(int)1e3 + 5], b, c; bool visited[(int)1e3 + 5], flag, ans = true; vector <vector <int> > adj((int)1e3 + 5); int main() { cin >> N >> M; while(M) cin >> b >> c, adj[c].push_back(b); for(int i = 0; i < N;++i) { cin >> a[i]; flag = true; visited[a[i]] = true; if(adj[a[i]].empty()) continue; for(int j = 0; j < adj[a[i]].size();++j) if(!visited[adj[a[i]][j]]) flag = false; if(!flag) ans = false; } if(!ans) cout <<"NO"; else cout << "YES"; } 
AC IN 0.234 SEC  abid1729  1280. Topological Sorting  25 Jun 2019 19:21  1 
#include<bits/stdc++.h> using namespace std; int main() { long long m,i,n,a[100005][2],k,b[1005]; cin>>n>>m; for(i=0;i<m;i++){ cin>>a[i][0]>>a[i][1]; } for(i=0;i<n;i++){ cin>>k; b[k]=i; } for(i=0;i<m;i++){ if(b[a[i][0]]>b[a[i][1]]){ cout<<"NO"; return 0; } } cout<<"YES"; } 
another tricky test case incase you get WA but don't know what to do . . .  Sam Green  1280. Topological Sorting  12 Jun 2019 21:59  2 
1 1 1 1 1 the answer must be "NO", not "YES" Edited by author 27.04.2007 09:34 My Program says "YES" and i got accepted 
O(n^3) got 0.826s AC!  paulzrm  1280. Topological Sorting  21 Jun 2018 17:34  1 
I can't belive it! for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(can[i][j]) for(k=1;k<=n;k++) if(can[j][k]) can[i][k]=1; } } 
WA#7  Loky_Yuri [USTU]  1280. Topological Sorting  3 Nov 2017 23:23  7 
WA#7 Loky_Yuri [USTU] 20 Dec 2006 19:51 This test is something like this 2 2 1 2 1 2 1 2 Correct answer is YES Thank. This test help me to get AC Re: WA#7 Mihran Hovsepyan {1 kurs of <RAU>} 5 Jun 2008 01:40 Thank you very much,but now I've WA#33. Re: WA#7 AYUBXON UBAYDULLAYEV TUIT 20 Apr 2013 12:10 Thanks for test, i got AC Re: WA#7 kaa..........ai 28 Jun 2013 14:44 Thanks a loooooooooooooooot! 
Weak Dataset  Saifullah Talukder  1280. Topological Sorting  25 Jul 2017 14:16  1 
I think the dataset for this problem is weak. I got AC without checking for cycles. Input: 3 3 1 3 3 2 2 1 1 3 2 Correct output: NO But my code ( http://ideone.com/ZljGZ5 ) returns YES and it got Accepted. Edited by author 25.07.2017 14:17 Edited by author 25.07.2017 14:18 
Can anyone explain 1# test case?  Just_do_it  1280. Topological Sorting  8 Feb 2017 13:01  2 
in 1 test case we can't determine whether subject 3 should be earlier than 4 or 4 than 3, because there's isn't any edge that show which one should be sdutied ealrier, why answer is YES???? I think if we can't verify it answer should be NO Verify correctness = see if there's such a pair in the first list, that goes in reverse order on the second list. For test 2 it's pairs (3 5), (5 2), (4 2), for test 1 there's no such pairs. 
WA#33  Anton [SUrSU#6]  1280. Topological Sorting  2 Oct 2016 22:16  9 
WA#33 Anton [SUrSU#6] 25 Jun 2006 01:42 Who can give me some tricky tests for this problem, please! May be you need a more tricky algo? It's unable to have WA with this problem (quite simple algo) Please help, i have the same problem but i don't know where is my error here is code #include <iostream> using namespace std; int power[1005]; int deg[1005]; int mas[1005][1005]; int n,m; int answers[1006]; void input() { cin>>n>>m; int a,b; for(int i=0;i<m;i++) { cin>>a>>b; mas[a][power[a]++] = b; deg[b]++; } for(int i=0;i<n;i++) cin>>answers[i]; } void solve() { for(int i=0;i<n;i++) { if (deg[answers[i]]>0) { cout<<"NO"; return; } for(int j=0;j<power[answers[i]];j++) deg[mas[answers[i]][j]] ; } cout<<"YES"; } int main() { input(); solve(); return 0; } Re: WA#33 Nechaev Ilya (Rybinsk SAAT) 10 Nov 2006 04:00 I don't know what are you doing, but you need just check M conditions for given sequence. I don't know what can be wrong. Edited by author 10.11.2006 04:29 Re: WA#33 Nechaev Ilya (Rybinsk SAAT) 10 Nov 2006 04:20 Haha. I just changed int mas[1005][1005]; to int mas[1005][10005]; and get AC. I think that each limitation can occur in the input more than once i.e. some limitations can be equal :p Advice: this solution use too much memory. Really you need less than 1 Mb. Edited by author 10.11.2006 14:02 Thank you for advise. Now i just changed adjanced list stored in array to vector<vector<int> > . And my programm used only 860 Kb. Haha. I just changed int mas[1005][1005]; to int mas[1005][10005]; and get AC. I think that each limitation can occur in the input more than once i.e. some limitations can be equal :p Advice: this solution use too much memory. Really you need less than 1 Mb. Edited by author 10.11.2006 14:02 I'm very appreciate you. I used vector<vector<int> > and eventually got AC:) Thank you for the advice about limitations! 
Tip for resolution  GastonFontenla  1280. Topological Sorting  9 Aug 2015 02:37  1 
You don't need to calculate the topological order. If you first calculate the topological order, and then try to "verify" the study order, will complicate a simple problem. 
WA8?  Илья  1280. Topological Sorting  28 Apr 2015 16:16  1 
WA8? Илья 28 Apr 2015 16:16 I dont understand why i get WA # 8 
Very very bad title  ucs6  1280. Topological Sorting  5 Jun 2014 01:44  2 
Don't be trapped by the title of this problem...it would just make it more complicated I see no problem in the title. It's a very simple straight forward TOP_SORT problem. And I have seen some critical cases in other threads which cases would appear 'critical' if and only if any process other than simple top_sort is approached. 
Why this problem has so high complexity estimation?  breezemaster  1280. Topological Sorting  25 Dec 2013 23:59  2 
It is very easy problem, i think complexity estimation 192 is overestimation. Very simple search was accepted: static bool Solve(IEnumerable<Tuple<int, int>> limitations, int[] proposedOrder) { foreach (Tuple<int, int> limitation in limitations) { int less = limitation.Item1; int greater = limitation.Item2; if (less == greater) return false; // wrong rule foreach (int currentSubj in proposedOrder) { if (currentSubj == greater) return false; // first is greater, so rule is contradicted if (currentSubj == less) break; // first is smaller, so rule is satisfied, go to next one } } return true; // all rules was satisfied } 1. Some time ago ML for it was 1MB. Try to solve within this limitation. 2. Average difficulty of a problem on Timus is ~1300, so 192 means that it is very simple problem (~15% of average difficulty), how did you get it is overestimation? 
0.79sec AC.My algo is O((m+n)lgm).But why it is so slow?  Andrew Yu  1280. Topological Sorting  21 Dec 2013 14:51  4 
hm... Dilyan 9 May 2005 05:28 for n = 10000 and m = 100000 you get approximately 2.10^6. the only way to get 0.79 is if the constant is big enough. mine is O(m + n) and I get 0.079 Re: hm... RedRick <<TSOGU>> 16 Sep 2009 22:19 my algo O(m+n) too, 0.046 s O(m+n^2) algo gets AC with 0.046 :D 
TL on test #15  Andy Pilate  1280. Topological Sorting  1 Oct 2013 05:06  1 

It is simple problem,Do you agree?  b4die  1280. Topological Sorting  23 Feb 2013 13:30  6 
No, I don't, idea is simple, but I have a problem: I get MLE of #15, and I can't fix it. I'we tried all ways of graph representation, but I always get MLE #15. Can someone please help me? Here is part of my code that uses the memory, the working part is eliminated: type TEdge=record i,j:integer end; var g:array[1..100001] of TEdge; st,deg:array[0..1001] of integer; sol:array[1..1000] of integer; n,m,i,k:integer; procedure sort(l,r:integer); var i,j:integer; k,t:TEdge; begin i:=l; j:=r; k:=g[(i+j) div 2]; while i<=j do begin while (g[i].i<k.i) or ((g[i].i=k.i) and (g[i].j<k.j)) do inc(i); while (k.i<g[j].i) or ((k.i=g[j].i) and (k.j<g[j].j)) do dec(j); if i<=j then begin t:=g[i]; g[i]:=g[j]; g[j]:=t; inc(i); dec(j) end end; if i<r then sort(i,r); if l<j then sort(l,j) end; begin assign(input,''); reset(input); readln(n,m); for i:=1 to n+1 do begin deg[i]:=0 end; for k:=1 to m do begin readln(g[k].i,g[k].j); inc(deg[g[k].j]) end; g[m+1].j:=0; g[m+1].i:=0; for i:=1 to n do read(sol[i]); sort(1,m); close(input); // working part goes here, cut because of fourth rule..... end. When i first time solution this problem o has WA and really don't understand WHY. But now i write a simple programm 20 lines and get AC. Sorry for my English. Edited by author 01.04.2005 20:05 Very simple... Edited by author 01.04.2005 20:08 Pls dont do any sort, just check for prerequisites of subjects in the left side of order for given subject. I think you should be able to get solution in O(N+M). 
Why WA #8 ?????  Bristy  1280. Topological Sorting  30 Nov 2012 17:52  2 
I have isolated the trees at first, then i ran a topsort. I dont understand why i get WA #8 It is not topological sorting task :) 
Really N<=1000  Eugene Zavgorodny  1280. Topological Sorting  13 Nov 2012 02:17  3 
I don't think, that N<=1000. Because when I submit mas[1001][1001], I get WA2. But when I submit mas[2000][2000], I get AC May be you use mas[i][j], where is i = 1001, j = 1001 or something like that My solution with mas[2000][2000] got WA 14 but with mas[3000][3000] got AC :) 
WA #5  Lebedev_Nicolay[Ivanovo SPU]  1280. Topological Sorting  10 May 2011 21:14  2 
WA #5 Lebedev_Nicolay[Ivanovo SPU] 28 Sep 2008 02:15 What is test #5. Please help! Re: WA #5 Denis Astanin (KPI) 10 May 2011 21:14 
If you have WA #31...  Smilodon_am [Obninsk INPE]  1280. Topological Sorting  20 Apr 2011 17:22  1 
This test perhaps contain double links between vertices... 