|
|
Страница 2 Just check if the condition for the i-th node is correct in the given order. That's it. ~8 lines or something. 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 #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"; } 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; } } 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:18in 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. What is Test #16? Please someone help! What is Test #16? Please someone help! Same here... got stuck in Test-16 . 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"; } 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. I dont understand why i get WA # 8 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? 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 :) Страница 1 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. I`d say don`t be trapped by the category of the problem. It says Graph Theory, but can be easily solved with other data structures. This test perhaps contain double links between vertices... What it can be???i have TL 15 if i change code i have wa 15 it's terrible) Sorry, my problem was in array)Read conditions more attentively, not as I))) for example test : 2 2 1 2 2 1 1 2 the answer is NO, not YES What is test #5. Please help! Some limitations are identical, and when I used counter for entering edges to each vertex, I get WA15). Edited by author 28.01.2008 12:26 |
|
|