|
|
Could you please show your solution or hint? I've been struggling hard to overcome WA 8... Then I've made these test cases and got AC in one go. I hope these tests will be helpful to overcome WA... :) Case 1: 4 3 0 4 0 1 0 2 0 Ans: 2 1 2 Case 2: 2 2 0 1 0 Ans: 1 1 Case 3: 3 2 3 0 1 3 0 1 2 0 Ans: 1 1 Case 4: 3 2 0 1 3 0 2 0 Ans: 2 1 3 Case 5: 4 2 4 0 1 0 4 0 1 3 0 Ans: 2 1 3 Case 6: 5 5 0 5 0 5 0 5 0 1 2 3 4 0 Ans: 4 1 2 3 4 Case 7: 5 2 0 1 0 5 0 5 0 3 4 0 Ans: 3 1 3 4 Let me know if any1 finds any error... Thanks. Edited by author 20.06.2016 22:19 My program passed all this tests but still I have WA7 write 7 test. Please. Did you find solution for 7th test? Test 7 please. Edited by author 27.11.2019 12:53 There cannot be any impossible case as is suggested by the very first line of the problem statement yes , no impossible cases are present. I recommend you this resource: https://e-maxx.ru/algo/bfsalso you can make a function instead of the lyambda, but I just like lyambdas more. #include <iostream> #include <vector> #include <queue> using namespace std; int main() { int N; cin >> N; vector <vector <int>> g(N); int h; for (int i = 0; i < N; i++) { for (;;) { cin >> h; if (!h) break; g[i].push_back(h - 1); } } int n = g.size(); queue<int> q; vector<bool> used(n); vector<int> d(n); int s; auto bfs = [&](int start) { s = start; q.push(s); used[s] = true; while (!q.empty()) { int v = q.front(); q.pop(); for (size_t i = 0; i<g[v].size(); ++i) { int to = g[v][i]; if (!used[to]) { used[to] = true; q.push(to); d[to] = d[v] + 1; } } } }; for (int start = 0; start < n; ++start) if (!used[start]) { bfs(start); } vector <int> ans; for (int i = 0; i < n; i++) { if (d[i] % 2 == 0) ans.push_back(i + 1); } int size = ans.size(); cout << size << '\n'; for (int i = 0; i < size; i++) cout << ans[i] << " "; } Edited by author 26.01.2019 22:53 Edited by author 30.01.2019 03:16My solution is crushed on 11 test. please help me... //problem solved (issue of different compilers of my local PC and judge one) Edited by author 26.03.2017 16:41 how can i see my current accepted submission rank???? http://acm.timus.ru/rating.aspx?space=1&num=1106Non language-specific rating; from there, you can select a language for a language-specific rating. However, it doesn't appear you have this task submitted, at least not from the account you've posted this message. Edited by author 10.11.2016 09:24 what's wrong with this code: #include <iostream> #include <vector> #include <list> using namespace std; int ar[102][102],viz[102]; int n; list <int> a; int dfs(int s) { viz[s] = 1; for (int i=1;i<=n;i++) { if (ar[i][s] && !viz[i]) {dfs(i); }//a.push_back(i);} } return 0; } int main() { cin >> n; int z; for (int i=1;i<=n;) { cin >> z; if (z == 0) i++; else ar[i][z] = 1; } dfs(1); for (int i=1;i<=n;i++) if(!viz[i]) a.push_back(i); cout << a.size() << endl; for (int n : a) { cout << n << " "; } return 0; } maybe i didn't understand problem properly,some help? 1. Answer always exists. 2. Use DFS for all unmarked vertices and mark them: if current vertex is marked as x, all next must be marked as (x + 1) % 2. (0->1, 1->0) 3. Then just print all vertices marked by 0 (or 1). Edited by author 26.06.2010 04:17 I think, it doesn't need to use DFS. If the edge hasn't incident edges that belong to the first team, we add this edge to the fisrt team. That's all:) If someone has no friends, there is no answer !! I think, it doesn't need to use DFS. If the edge hasn't incident edges that belong to the first team, we add this edge to the fisrt team. That's all:) Thanks, you very helped me) my code is running correctly but yet it fails at test 1 :( Earlier I had got a WA 9 but now I'm getting a WA 5 with the same code. What's the logic? #include <iostream> using namespace std; long f[101],n; int main() { long i,t,c=0; cin>>n; for (i=1;i<=n;i++) { if (f[i]==0) f[i]=1; while (true) { cin>>t; if (t==0) break; if (f[t]==0) f[t]=1+(f[i]==1); } if (f[i]==1) c++; } cout<<c<<endl; for (i=1;i<=n;i++) if (f[i]==1) cout<<i<<" "; } why?? I had WA 11, this test helped me: 4 2 0 1 4 0 4 0 2 3 0 Edited by author 30.10.2007 04:07 What's the main idea behind it? I am getting a wrong answer in it. Can anyone please help me? Is there any better solution? No. This is the lower bound, since you have to read the edges anyways. But established it with an error which makes me WA #13. Guess cases before #13 are simple with no big number of vex. Use BFS - i get AC. Make array size as n items. Rules for filling: 0 items equals -1, if first elements have childs them set 1 and use recurce. WA 6 3 2 0 1 3 0 2 0 ----- 2 1 3 3 2 3 0 1 0 1 0 -- 1 1 WA 11 4 2 0 1 4 0 4 0 2 3 0 -- 2 1 3 WA 13 3 3 0 3 0 1 2 0 -- 2 1 2 Hi, I have a solution which seems correct. For the first test it gives me the following answer: 4 1 4 5 6 I consider, it fits to the problem statement. Could anyone clarify, what is going wrong? My algorithm is based on BFS and I always mark start vertex in a connected component as a first team vertex. |
|
|