Show all threads Hide all threads Show all messages Hide all messages 
WA on 6. Can anyone tell me why?  raphaelrbr  1671. Anansi's Cobweb  17 Mar 2019 04:29  1 
#include <bits/stdc++.h> using namespace std; #define ll long long #define F first #define S second #define mp make_pair #define pii pair<int,int> #define vi vector<int> #define pq priority_queue #define pb push_back #define watch(x) cout << (#x) << " is " << (x) << endl #define ALL(a) (a.begin()),(a.end()) #define FOR(x,to) for(x=0;x<(to);x++) #define FORI(a,b) for(int i = a; i<b; i++) #define fastio ios::sync_with_stdio(0); cin.tie(NULL); const int INF = 0x3f3f3f3f; struct ar{ ll x,y; }; ar v[100100]; int p[100100] = {0}; ll id[100100]; ll sz[100100]; ll num; ll find(ll x){ if(id[x] == x) return x; return id[x] = find(id[x]); } void join(ll x, ll y){ ll p = find(x); ll q = find(y); if(p==q) return; num; if(sz[p] > sz[q]) { ll t = q; p = q; q = t; } id[p] = q; sz[p] += sz[q]; } int main(){ fastio ll n,m,i,q; cin >> n >> m; num = n; ll arf[100100]; ll ans[100100];
FOR(i,m){ cin >> v[i+1].x >> v[i+1].y; } FOR(i,m+1){ id[i+1] = i+1; sz[i+1] = 1; } cin >> q; FOR(i,q){ ll x; cin >> x; p[x] = 1; arf[qi] = x; } FOR(i,m+1){ if(i==0) continue; if(!p[i]){ join(v[i].x, v[i].y); } }
ans[q] = num; for(int i = 1; i<=q; i++){ join(v[arf[i]].x, v[arf[i]].y);
ans[qi] = num;
}
for(int i = 1; i<=q; i++){ cout << ans[i] << " "; }
cout << "\n"; return 0; }
Edited by author 17.03.2019 04:30 
GOOD peoples Please help me :(  Enigma [UB of TUIT]  1671. Anansi's Cobweb  28 Feb 2019 16:14  6 
GOOD peoples Please help me! I have got WA#5! I used DSU!! My program gives right answer for all my tests! But again WA#5 and I can not found my mistake! I shall wait advices or tests! Thank you advance!!! What test you used to check it? 4 4 1 2 1 2 2 3 3 4 3 1 2 3 good luck!!! 
Some hint  Adilbek_  1671. Anansi's Cobweb  11 Sep 2018 04:16  2 

What about WA16 ?  Khujamurod  1671. Anansi's Cobweb  9 Aug 2017 13:41  8 
I used DSU and I have WA16. Can you help me? I can't help you without code. I have never WA#16. I only have several MLE's before AC. "/* const int maxn = 100100; int a[maxn], b[maxn], c[maxn]; bool order[maxn]; int cnt; int p[maxn], rank[maxn]; int find_set(int x) { if(p[x] == x) return x; return p[x] = find_set(p[x]); } int unite(int x, int y) { x = find_set(x); y = find_set(y); if(x == y) return 0; if(rank[x] > rank[y]) { p[y] = x; } else { p[x] = y; if(rank[x] == rank[y]) rank[y] ++; } return 1; } int main() {
int n, m, q; scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++) { scanf("%d%d", a + i, b + i); } scanf("%d", &q); for (int i = 0; i < q; i ++) { scanf("%d", c + i); order[c[i]] = true; } for (int i = 0; i < n; i ++) p[i] = i; cnt = n; for (int i = 0; i < n; i ++) { if(order[i] == false) { cnt = unite(a[i], b[i]); } }
c[q] = cnt; for (int i = q  1; i > 0; i ) { cnt = unite(a[c[i]], b[c[i]]); c[i] = cnt; } for (int i = 1; i < q; i ++) printf("%d ", c[i]); printf("%d", c[q]); }*/" You have a cycle where you are calculating cnt for q. The limit is wrong. i<n is wrong. i<m is correct. Because of m is number of edges not n. I changed n to m in your code and got AC again. Thanks Mahilewets!!! Is your idea same or not ? Idea is the same. I was getting MLE because of critical mistake in find_set. There was an iterative implementation. My iterative function was equivalent to : return (par[x] == x) ? x : par[x] =find_set (x) ; Thanks for your answer ! cause i made the same problem! The good part is Initially I made such mistakes incredible often But after only few months of regular basis practice Such blunders almost completely disappeared 
test  Gleb_Kazantaev(NNSTU)  1671. Anansi's Cobweb  18 Jul 2017 19:53  2 
test Gleb_Kazantaev(NNSTU) 2 Nov 2014 02:46 5 7 1 2 2 3 1 4 4 5 1 5 2 5 4 3 4 3 4 7 2 ans: 1 1 2 3 Re: test Амир Меннибаев 18 Jul 2017 19:53 
Why MLE is given on test 5?  Ehsan Raeyatpisheh  1671. Anansi's Cobweb  4 May 2015 22:23  2 
I am not allocating any memory in heap, everything is defined globally, why do I get Memory Limit Exceeded error on test 5? Why this error is not given for test 1? I'm not even using STL. It also happened to me solving another problem(1220. Stacks), I got memory limit exceeded on test 10, same situation as here. Does IO operations use memory? I assume I get this error as testcases get larger in size... (I also tried disabling IO buffering) Solved. It was a problem with my DSU function. 
identical threads?  Jurca Razvan  1671. Anansi's Cobweb  22 Nov 2014 06:59  3 
Can there be identical threads in the test? Like: 4 4 1 2 1 2 2 3 3 4 3 1 2 3 And if they can occur is the answer 2 2 3 or 1 2 3? My program gives: 1 2 3 I got AC. It is a web. The web is not a multigraph. All edges will be unique. 
Different answer in different language?  wxy  1671. Anansi's Cobweb  24 Jul 2014 00:03  2 
I solve this problem with C++ first and got WA#6, but I can't find where is my problem, so I rewrite it with C# with the same solution, but to my surprise, this time I got AC. And even till now I don't know what are the differences between my two lovely code. Any idea? //Sorry for my poor English Idea  those two solutions are not the same really. What else do you expect w/o any code? BTW, you can write random generator of big tests and run and compare outputs of two solutions till you'll find a difference. 
WA on #5 Why?  yuhc  1671. Anansi's Cobweb  19 Nov 2013 22:41  4 
I don't think there are such threads as (2 Edges) 1 2 2 1 And although my program can solve that case, I still WA on test5. Can you help me and give me some advice? Thank you very much! Use union+Rank can AC.... Use union+Rank can AC.... Try this test: 4 4 1 2 1 2 2 3 3 4 3 1 2 3 Answer 1 2 3 
WA#5  KravetsSSAU  1671. Anansi's Cobweb  19 Nov 2013 22:40  7 
WA#5 KravetsSSAU 21 Jan 2009 21:59 Re: WA#5 Protsenko_vladimir_ssau 22 Jan 2009 16:11 4 4 ** 4 4 1 2 ** 1 4 1 3 ** 2 3 2 3 ** 2 4 3 4 ** 3 4 1 **** 1 4 **** 4 maybe it can help Edited by author 22.01.2009 16:27 Re: WA#5 hello_world_ww 20 Jan 2013 09:09 it's 2 1 ,my code work ok ,but wrong #5 ,where? Edited by author 20.01.2013 09:13 Re: WA#5 Pavel Khaustov [Tomsk PU] 14 Jul 2009 23:15 Try this test case: 4 5 1 2 2 3 3 4 4 2 1 3 5 1 2 3 4 5 The answer is: 1 1 2 3 4 Re: WA#5 hello_world_ww 20 Jan 2013 09:14 my code do that is right ,but... wa 5 Snayde [Shevchenko NUK] 19 Nov 2013 22:40 Try this test: 4 4 1 2 1 2 2 3 3 4 3 1 2 3 Answer: 1 2 3 
For those who have TLE on 15  vicproon  1671. Anansi's Cobweb  5 Jul 2013 21:48  2 
I had the same problem, and solved it after changing all c++ io functions from <iostream> to <cstdio> Thanks, your hint really helped me. The same thing in Java. I had TLEon15. After I replaced Scanner with my custom input parsing I had got AC. 
TLE #12 ?  hello_world_ww  1671. Anansi's Cobweb  9 Jun 2013 16:00  2 
I use Disjointset who can help me? Re: TLE #12 ? SamGTU7_Kareva Nadezhda Vladimirovna 9 Jun 2013 16:00 
crash #9  sysu2012zzp  1671. Anansi's Cobweb  25 Oct 2012 07:50  1 
I use graph to solve this problem but initially get MLE. Then I reduce the size of array because of the matrix is a Symmetric Matrix. However,finaly crash at test #9. Can somebody give me some tips? 
Guys I got a ques.  Ibragim Atadjanov (Tashkent U of IT)  1671. Anansi's Cobweb  27 Apr 2011 21:46  1 
If its not a multy eadge and it is a bridge, then it increase the number of pieces by one otherwise the pieces amount left same. Am I right? 
No subject  napst101r  1671. Anansi's Cobweb  11 Jul 2010 23:07  1 
Edited by author 11.07.2010 23:42 
DSU rules!!! ()  Lord(Mamin Oleg)  1671. Anansi's Cobweb  5 Apr 2010 18:01  2 
Sure ;) By the way my DSU got AC with 0.109 sec time and 2 178 KB memory. WHat about you? 
WA#25: can you give me some tests?  fail  1671. Anansi's Cobweb  15 Jan 2010 22:13  2 
I got AC when i handle multigraphs (multiple edges between pair of vertices are possible) Look my post (he located above your post in that node{ NOT MAIN NODE BUT NODE of the problem 1671}) there you can find test with multiedges. Edited by author 15.01.2010 22:18 Edited by author 16.01.2010 13:03 
edgesduplicates  Baurzhan  1671. Anansi's Cobweb  6 Nov 2009 22:39  2 
Are there multiple egdes in the tests? A have WA 25 and i don't process this case. I think there are no multiple edges because [don't_processing_multiple_edges_programm] can't pass 25 tests. Can anybody give me 25 test or some hints? P.S I use dsu with heuristics. Now I got AC. There can be tests with multiedges for example 2 2 1 2 2 1 1 1 answer is 1. Also, don't use STL to avoid TLE. 
WA#4  [SSAU] Igor Shamashov  1671. Anansi's Cobweb  17 Feb 2009 01:38  3 
WA#4 [SSAU] Igor Shamashov 22 Jan 2009 13:01 Can you give me some tricky tests, please? Re: WA#4 Crash_access_violation 17 Feb 2009 01:27 I got wa4 too. Maybe we don't undestand the task... Please give some tests. thX Re: WA#4 Crash_access_violation 17 Feb 2009 01:38 what answer for this test? 4 4 1 4 4 1 1 4 4 1 4 4 3 1 2 my ans : 3 3 3 4 
I did not get it, can someone explain to me this ?  Madi  1671. Anansi's Cobweb  11 Jan 2009 21:34  2 
You are given a graph, and in each step you cut (remove) one of the edges, you must output (in each step) the amount of components in the new graph. Edited by author 11.01.2009 21:35 