Submission #58283044

Source Code Expand

#include <bits/stdc++.h>
#define int long long	
using namespace std;
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=998244353;
const int maxn=2e6+10;
const int inf=1e9+7;
int n,m;
struct no
{
	int x,y,v;
	inline friend bool operator < (no x,no y)
	{
		return x.v<y.v;
	}
}edge[maxn];
int fa[maxn],ans,cnt,sum;
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
signed main()
{
#ifdef Lydic
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	cin>>n>>m;
	for(int i=1;i<=m;i++){edge[i]={read(),read(),read()};sum+=edge[i].v;}
	for(int i=1;i<=n;i++)fa[i]=i;	
	sort(edge+1,edge+m+1);
	for(int i=1;i<=m;i++)
	{
		int fx=gf(edge[i].x),fy=gf(edge[i].y);
		if(fx!=fy)
		{
			fa[fx]=fy;
            ans+=edge[i].v;
		}
		else if(edge[i].v<0)
		{
			ans+=edge[i].v;
		}
	}
	cout<<sum-ans;
	return 0;
}

Submission Info

Submission Time
Task E - Destruction
User Lydic
Language C++ 20 (gcc 12.2)
Score 500
Code Size 992 Byte
Status AC
Exec Time 33 ms
Memory 9248 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 3500 KiB
hand_02.txt AC 1 ms 3484 KiB
random_01.txt AC 28 ms 8192 KiB
random_02.txt AC 5 ms 4312 KiB
random_03.txt AC 22 ms 6852 KiB
random_04.txt AC 4 ms 4148 KiB
random_05.txt AC 6 ms 4596 KiB
random_06.txt AC 17 ms 6724 KiB
random_07.txt AC 25 ms 7852 KiB
random_08.txt AC 26 ms 8056 KiB
random_09.txt AC 21 ms 7292 KiB
random_10.txt AC 24 ms 7968 KiB
random_11.txt AC 26 ms 8476 KiB
random_12.txt AC 22 ms 7372 KiB
random_13.txt AC 33 ms 9248 KiB
random_14.txt AC 28 ms 8684 KiB
random_15.txt AC 18 ms 6812 KiB
random_16.txt AC 17 ms 6704 KiB
random_17.txt AC 31 ms 9244 KiB
random_18.txt AC 24 ms 7812 KiB
sample_01.txt AC 1 ms 3508 KiB
sample_02.txt AC 1 ms 3500 KiB
sample_03.txt AC 1 ms 3504 KiB