Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

DontLookBack's blog

By DontLookBack, history, 4 weeks ago, In English,

This problem : https://codeforces.com/contest/893/problem/C gives MLE on test 10. However for other tests same the size of test 10 it doesnt give MLE, I checked for array bounds and everything, it seems to be fine.

Here is what I did :

#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
const ll maxn=1e5+2;
const ll mod=3e18;
vector<vector<ll>> g(maxn);
vector<bool> vis(maxn,false);

void dfs(int v,int p){
	vis[v]=true;
	for(ll to : g[v])
		if(to!=p)
			dfs(to,v);
}
int main(){
	fast;
	ll n,m,i,j,k,x,u,v,f=0;
	cin>>n>>m;
	vector<pi> c;
	for(i=0;i<n;i++){
		cin>>x;
		c.pb({x,i});
	}
	
	sort(all(c));
	for(i=0;i<m;++i){
		cin>>u>>v;
		--u;
		--v;
		g[u].pb(v);
		g[v].pb(u);
	}
	
	ll ans=0;
	for(auto [cost,node] : c){
		if(!vis[node]){
			ans+=cost;
			dfs(node,-1);
		}
	}
	cout<<ans;
}

Submission if you want to review test cases : 82712538

Any help is appreciated and please dont downvote unecessarily.

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

try this test case

3 3
1 1 1
1 2
2 3
3 1
  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    So basically when values of all coins are equal it gives RE. like for example:

    5 5

    7 7 7 7 7

    1 2

    2 3

    3 4

    4 5

    1 3

    I dont get why.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no, i dont mean that, try to debug your dfs

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah I saw that it was going into infinite loop but this dfs doesnt fail for other cases and I have used this style of dfs for a while. I cant spot the error.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the help!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your dfs is well suited for trees and not all graphs in general. Try changing your dfs function to this:

void dfs(int v){
  vis[v]=true;
  for(ll to : g[v])
	if(!vis[to])
		dfs(to);
}

It passed all tests have look at my submissions.