366D - Dima and Trap Graph - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int i,j,n,m,x,y,ans,f[1010];
struct node{int x,y,l,r;}a[3030];
bool cmp(node x,node y){return x.r>y.r;}
int find(int x){return (f[x]==x)?x:f[x]=find(f[x]);}
int main(){
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;i++) scanf("%d %d %d %d",&a[i].x,&a[i].y,&a[i].l,&a[i].r);
	sort(a+1,a+1+m,cmp);
	for (i=1;i<=m;i++){
		for (j=1;j<=n;j++) f[j]=j;
		for (j=1;j<=m;j++)
			if (a[i].l>=a[j].l&&a[i].l<=a[j].r){
				x=find(a[j].x);y=find(a[j].y);
				if (x!=y) f[x]=y;
				if (find(1)==find(n)) {ans=max(ans,a[j].r-a[i].l+1);break;}
		}
	}
	if (!ans) printf("Nice work, Dima!\n");
	else printf("%d\n",ans);
	return 0;
}