Show all threads Hide all threads Show all messages Hide all messages |
Test for WA#5 | Pat | 1671. Anansi's Cobweb | 30 Mar 2023 13:07 | 1 |
5 8 2 3 1 2 2 5 1 4 1 5 3 4 3 4 4 4 8 7 6 8 2 3 4 5 1 > 1 1 1 1 2 3 4 5 |
Idea | Hristo Nikolaev (B&W) | 1671. Anansi's Cobweb | 29 Mar 2023 21:04 | 1 |
Idea Hristo Nikolaev (B&W) 29 Mar 2023 21:04 Instead of doing the cuts in the order given in the input, I found it easier to do it in reverse order, so we get merging instead of cutting. Edited by author 29.03.2023 21:05 |
test | Gleb_Kazantaev(NNSTU) | 1671. Anansi's Cobweb | 5 Mar 2022 23:50 | 3 |
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 Re: test Prabhvir Singh Babra 5 Mar 2022 23:50 Thank you so much! This really helped me debug :). |
hint | Anton | 1671. Anansi's Cobweb | 29 Aug 2021 01:02 | 1 |
hint Anton 29 Aug 2021 01:02 |
TLE #12 ? | hello_world_ww | 1671. Anansi's Cobweb | 12 Jan 2021 01:00 | 5 |
I use Disjoint-set who can help me? Re: TLE #12 ? SamGTU7_Kareva Nadezhda Vladimirovna 9 Jun 2013 16:00 Try changing a linear search you might have into smth that can b done in constant time. That made it much faster for me. (hint: you probably don't need anything special, just change your implementation a bit) |
TLE#9 C# how make it faster? =( | Shamov Roman | 1671. Anansi's Cobweb | 24 Nov 2020 12:50 | 2 |
Can someone help how to make C# code faster? Here is my code: using System; using System.Collections.Generic; class Program { static int countCut(List<int>[] nods, List<int> uncheckedNodes) { int next = 0; int count = 0; do { count++; watchCut(nods, uncheckedNodes, next); if (uncheckedNodes.Count > 0) next = uncheckedNodes[0]; else next = -1; } while (next != -1); return count; } static void watchCut(List<int>[] nods, List<int> uncheckedNodes, int node) { uncheckedNodes.Remove(node); for (int i = 0; i < nods[node].Count; i++) { if (uncheckedNodes.Contains(nods[node][i])) watchCut(nods, uncheckedNodes, nods[node][i]); } } static void Main(string[] args) { string[] inp_NM = Console.ReadLine().Split(' '); int N, M; N = Convert.ToInt32(inp_NM[0]); M = Convert.ToInt32(inp_NM[1]); int[,] threads = new int[M, 2]; List<int>[] nods = new List<int>[N]; for (int i = 0; i < N; i++) nods[i] = new List<int>(); for (int i = 0; i < M; i++) { string[] inp_thread = Console.ReadLine().Split(' '); threads[i, 0] = Convert.ToInt32(inp_thread[0]) - 1; threads[i, 1] = Convert.ToInt32(inp_thread[1]) - 1; nods[threads[i, 0]].Add(threads[i, 1]); nods[threads[i, 1]].Add(threads[i, 0]); } int Q; Q = Convert.ToInt32(Console.ReadLine()); int[] cuts = new int[Q]; string[] inp_tear = Console.ReadLine().Split(' '); for (int i = 0; i < Q; i++) { cuts[i] = Convert.ToInt32(inp_tear[i]) - 1; } for (int i = 0; i < Q; i++) { nods[threads[cuts[i], 0]].Remove(threads[cuts[i], 1]); nods[threads[cuts[i], 1]].Remove(threads[cuts[i], 0]); List<int> uncheckedNodes = new List<int>(); for (int l = 0; l < N; l++) uncheckedNodes.Add(l); Console.Write(countCut(nods, uncheckedNodes)+" "); } } } Edited by author 24.11.2020 08:00 In this problem you should use disjoint-set(система непересекающихся множеств). |
For wa#25 | guilty spark | 1671. Anansi's Cobweb | 7 Sep 2020 15:22 | 1 |
There can be multiple edges. For instance: 1 2 2 1 Using a set will give WA. Try multi-set or some other data structure in c++. Edited by author 07.09.2020 15:22 Edited by author 07.09.2020 15:22 |
sorry but why WA4? | qulinxao | 1671. Anansi's Cobweb | 24 Aug 2020 04:03 | 1 |
hm.ok Edited by author 25.08.2020 03:14 |
What about WA16 ? | Khujamurod | 1671. Anansi's Cobweb | 20 May 2020 00:58 | 9 |
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 i do exactly same mistake and get wa at test 16 thnx Mahilewets Nikita [BSUIR] |
Help!WA#11 | miao22 | 1671. Anansi's Cobweb | 30 Jan 2020 18:15 | 3 |
#include<bits/stdc++.h> using namespace std; int n,m,q,a[100003],b[100003],c[100003]; vector<pair<int,int> >v; vector<int>g[100003]; bool vis[100003]; int qq[100003]; map<int,int>mp; void dfs(int x,int cc){ vis[x]=1; for(int i=0;i<g[x].size();i++) if(!vis[g[x][i]]) dfs(g[x][i],cc); qq[x]=cc; } int main(){ cin>>n>>m; for(int i=0;i<m;i++) cin>>a[i]>>b[i], a[i]--, b[i]--; cin>>q; for(int i=0;i<q;i++)cin>>c[i],c[i]--,v.push_back(make_pair(a[c[i]],b[c[i]])),a[c[i]]=b[c[i]]=-1; reverse(c,c+n);reverse(v.begin(),v.end()); for(int i=0;i<m;i++) if(a[i]!=-1) g[a[i]].push_back(b[i]), g[b[i]].push_back(a[i]); int cnt=0; for(int i=0;i<n;i++) if(!vis[i]) mp[cnt]=cnt, dfs(i,cnt++); vector<int>ans; for(int i=0;i<q;i++){ ans.push_back(cnt); if(mp[qq[v[i].first]]!=mp[qq[v[i].second]]) mp[qq[v[i].first]]=mp[qq[v[i].second]], qq[v[i].first]=qq[v[i].second], cnt--; } reverse(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) cout<<ans[i]<<' '; } 5 8 2 3 1 2 2 5 1 4 1 5 3 4 3 4 4 4 8 7 6 8 2 3 4 5 1 |
unable to understand first example. can anyone please kindly explain. | anupam ghosh | 1671. Anansi's Cobweb | 30 Dec 2019 17:16 | 1 |
unable to understand first example. can anyone please kindly explain. |
WA#5 | KravetsSSAU | 1671. Anansi's Cobweb | 23 Jun 2019 18:08 | 8 |
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 my program run all the test and they are all corret |
Guys I got a ques. | Ibragim Atadjanov (Tashkent U of IT) | 1671. Anansi's Cobweb | 12 Jun 2019 21:19 | 2 |
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? It is so hard to solve it this way, because you have to recalculate bridges after every delete. You should try disjoint-set-union this data structure is so awesome and simple to write. |
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[q-i] = 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[q-i] = 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 |
|
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 test-cases 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 |