106362024-04-07 15:06:36111Varázserdőcpp17Időlimit túllépés 50/1005.076s113356 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);
	for(int i=0;i<M;i++){
		auto[c,a,b]=e[i];
		w[a]+=v[b]+1;
		w[a]%=MOD;
		w[b]+=v[a]+1;
		w[b]%=MOD;
		int cc=i+1==M?c+2:get<0>(e[i+1]);
		if(c!=cc){
			for(int i=1;i<=N;i++){
				if(c+1==cc){
					v[i]=w[i];
				}
				else{
					v[i]=0;
				}
				ans+=w[i];
				ans%=MOD;
				w[i]=0;
			}
		}
	}
	ans+=MOD-M;
	ans%=MOD;
	cout<<ans<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva3ms2020 KiB
3Elfogadva3ms2236 KiB
subtask27/7
4Elfogadva3ms2448 KiB
5Elfogadva3ms2572 KiB
6Elfogadva13ms3404 KiB
7Elfogadva13ms3520 KiB
8Elfogadva1.741s50216 KiB
9Elfogadva1.743s58780 KiB
10Elfogadva1.736s67324 KiB
11Elfogadva1.74s75792 KiB
12Elfogadva1.726s84468 KiB
13Elfogadva1.725s89264 KiB
subtask39/9
14Elfogadva3ms50600 KiB
15Elfogadva3ms50732 KiB
16Elfogadva52ms58196 KiB
17Elfogadva252ms77268 KiB
18Elfogadva544ms113320 KiB
19Elfogadva514ms113204 KiB
20Elfogadva510ms113356 KiB
subtask414/14
21Elfogadva3ms50812 KiB
22Elfogadva2ms50904 KiB
23Elfogadva2ms50804 KiB
24Elfogadva2ms50812 KiB
subtask520/20
25Elfogadva3ms50824 KiB
26Elfogadva4ms51040 KiB
27Elfogadva4ms51036 KiB
28Elfogadva4ms51044 KiB
29Elfogadva4ms51040 KiB
30Elfogadva4ms51036 KiB
31Elfogadva4ms51048 KiB
32Elfogadva4ms51048 KiB
subtask60/50
33Elfogadva8ms51536 KiB
34Elfogadva68ms58588 KiB
35Elfogadva497ms98008 KiB
36Elfogadva507ms98008 KiB
37Elfogadva578ms113260 KiB
38Elfogadva662ms113268 KiB
39Időlimit túllépés5.065s81540 KiB
40Időlimit túllépés5.076s81504 KiB
41Elfogadva517ms100940 KiB