Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Test for WA#5 | Pat | 1671. Паутина Ананси | 30 мар 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. Паутина Ананси | 29 мар 2023 21:04 | 1 |
Idea Hristo Nikolaev (B&W) 29 мар 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. Паутина Ананси | 5 мар 2022 23:50 | 3 |
test Gleb_Kazantaev(NNSTU) 2 ноя 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 июл 2017 19:53 Re: test Prabhvir Singh Babra 5 мар 2022 23:50 Thank you so much! This really helped me debug :). |
hint | Anton | 1671. Паутина Ананси | 29 авг 2021 01:02 | 1 |
hint Anton 29 авг 2021 01:02 |
TLE #12 ? | hello_world_ww | 1671. Паутина Ананси | 12 янв 2021 01:00 | 5 |
I use Disjoint-set who can help me? Re: TLE #12 ? SamGTU7_Kareva Nadezhda Vladimirovna 9 июн 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. Паутина Ананси | 24 ноя 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. Паутина Ананси | 7 сен 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. Паутина Ананси | 24 авг 2020 04:03 | 1 |
hm.ok Edited by author 25.08.2020 03:14 |
What about WA16 ? | Khujamurod | 1671. Паутина Ананси | 20 май 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. Паутина Ананси | 30 янв 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. Паутина Ананси | 30 дек 2019 17:16 | 1 |
unable to understand first example. can anyone please kindly explain. |
WA#5 | KravetsSSAU | 1671. Паутина Ананси | 23 июн 2019 18:08 | 8 |
WA#5 KravetsSSAU 21 янв 2009 21:59 Re: WA#5 Protsenko_vladimir_ssau 22 янв 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 янв 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 июл 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 янв 2013 09:14 my code do that is right ,but... wa 5 Snayde [Shevchenko NUK] 19 ноя 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. Паутина Ананси | 12 июн 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. Паутина Ананси | 17 мар 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. Паутина Ананси | 28 фев 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. Паутина Ананси | 11 сен 2018 04:16 | 2 |
|
Why MLE is given on test 5? | Ehsan Raeyatpisheh | 1671. Паутина Ананси | 4 май 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. Паутина Ананси | 22 ноя 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. Паутина Ананси | 24 июл 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. Паутина Ананси | 19 ноя 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 |