106392024-04-07 15:15:22111Varázserdőcpp17Elfogadva 100/100584ms35600 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms228 KiB
2Elfogadva3ms484 KiB
3Elfogadva3ms356 KiB
subtask27/7
4Elfogadva3ms528 KiB
5Elfogadva3ms484 KiB
6Elfogadva7ms868 KiB
7Elfogadva7ms892 KiB
8Elfogadva300ms23800 KiB
9Elfogadva279ms23800 KiB
10Elfogadva289ms23908 KiB
11Elfogadva275ms23780 KiB
12Elfogadva268ms23908 KiB
13Elfogadva261ms23844 KiB
subtask39/9
14Elfogadva3ms632 KiB
15Elfogadva3ms632 KiB
16Elfogadva52ms5168 KiB
17Elfogadva256ms14504 KiB
18Elfogadva584ms35600 KiB
19Elfogadva541ms35484 KiB
20Elfogadva514ms35504 KiB
subtask414/14
21Elfogadva3ms360 KiB
22Elfogadva3ms356 KiB
23Elfogadva2ms356 KiB
24Elfogadva3ms392 KiB
subtask520/20
25Elfogadva3ms356 KiB
26Elfogadva4ms612 KiB
27Elfogadva4ms484 KiB
28Elfogadva4ms660 KiB
29Elfogadva4ms372 KiB
30Elfogadva4ms500 KiB
31Elfogadva4ms500 KiB
32Elfogadva4ms744 KiB
subtask650/50
33Elfogadva7ms868 KiB
34Elfogadva54ms5124 KiB
35Elfogadva504ms24092 KiB
36Elfogadva514ms23980 KiB
37Elfogadva537ms35444 KiB
38Elfogadva550ms35556 KiB
39Elfogadva568ms35588 KiB
40Elfogadva561ms35556 KiB
41Elfogadva519ms26268 KiB