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 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 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 Thank you so much! This really helped me debug :). I use Disjoint-set who can help me? Facing the same. 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) 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(система непересекающихся множеств). 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 hm.ok Edited by author 25.08.2020 03:14 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] #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]<<' '; } are there any test? 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. gimme test, please) 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 it's 2 1 ,my code work ok ,but wrong #5 ,where? Edited by author 20.01.2013 09:13 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 my code do that is right ,but... 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 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. #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! 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!!! I have got AC!!! =) What test you used to check it? 4 4 1 2 1 2 2 3 3 4 3 1 2 3 good luck!!! 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. 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. 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. 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 |
|