Submission #10,639

2024-04-07 15:15:22

cpp17

Accepted 100/100

584ms

35600 KiB

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define MOD 1000000007

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<tuple<int,int,int>>e(M);
	for(int i=0;i<M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		e[i]={c,a,b};
	}
	sort(e.begin(),e.end());
	int ans=0;
	vector<int>v(N+1),w(N+1),l(N+1);
	for(int i=0;i<M;i++){
		auto[c,a,b]=e[i];
		if(l[a]!=c){
			ans+=w[a];
			v[a]=l[a]+1==c?w[a]:0;
			w[a]=0;
			l[a]=c;
		}
		if(l[b]!=c){
			ans+=w[b];
			v[b]=l[b]+1==c?w[b]:0;
			w[b]=0;
			l[b]=c;
		}
		w[a]+=v[b]+1;
		w[a]%=MOD;
		w[b]+=v[a]+1;
		w[b]%=MOD;
	}
	for(int i=1;i<=N;i++){
		ans+=w[i];
	}
	ans+=MOD-M;
	ans%=MOD;
	cout<<ans<<'\n';
	return 0;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	2ms	228 KiB
		2	Accepted	3ms	484 KiB
		3	Accepted	3ms	356 KiB
subtask2	7/7
		4	Accepted	3ms	528 KiB
		5	Accepted	3ms	484 KiB
		6	Accepted	7ms	868 KiB
		7	Accepted	7ms	892 KiB
		8	Accepted	300ms	23800 KiB
		9	Accepted	279ms	23800 KiB
		10	Accepted	289ms	23908 KiB
		11	Accepted	275ms	23780 KiB
		12	Accepted	268ms	23908 KiB
		13	Accepted	261ms	23844 KiB
subtask3	9/9
		14	Accepted	3ms	632 KiB
		15	Accepted	3ms	632 KiB
		16	Accepted	52ms	5168 KiB
		17	Accepted	256ms	14504 KiB
		18	Accepted	584ms	35600 KiB
		19	Accepted	541ms	35484 KiB
		20	Accepted	514ms	35504 KiB
subtask4	14/14
		21	Accepted	3ms	360 KiB
		22	Accepted	3ms	356 KiB
		23	Accepted	2ms	356 KiB
		24	Accepted	3ms	392 KiB
subtask5	20/20
		25	Accepted	3ms	356 KiB
		26	Accepted	4ms	612 KiB
		27	Accepted	4ms	484 KiB
		28	Accepted	4ms	660 KiB
		29	Accepted	4ms	372 KiB
		30	Accepted	4ms	500 KiB
		31	Accepted	4ms	500 KiB
		32	Accepted	4ms	744 KiB
subtask6	50/50
		33	Accepted	7ms	868 KiB
		34	Accepted	54ms	5124 KiB
		35	Accepted	504ms	24092 KiB
		36	Accepted	514ms	23980 KiB
		37	Accepted	537ms	35444 KiB
		38	Accepted	550ms	35556 KiB
		39	Accepted	568ms	35588 KiB
		40	Accepted	561ms	35556 KiB
		41	Accepted	519ms	26268 KiB