10636 2024. 04. 07 15:06:36 111 Varázserdő cpp17 Időlimit túllépés 50/100 5.076s 113356 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 3ms 2020 KiB
3 Elfogadva 3ms 2236 KiB
subtask2 7/7
4 Elfogadva 3ms 2448 KiB
5 Elfogadva 3ms 2572 KiB
6 Elfogadva 13ms 3404 KiB
7 Elfogadva 13ms 3520 KiB
8 Elfogadva 1.741s 50216 KiB
9 Elfogadva 1.743s 58780 KiB
10 Elfogadva 1.736s 67324 KiB
11 Elfogadva 1.74s 75792 KiB
12 Elfogadva 1.726s 84468 KiB
13 Elfogadva 1.725s 89264 KiB
subtask3 9/9
14 Elfogadva 3ms 50600 KiB
15 Elfogadva 3ms 50732 KiB
16 Elfogadva 52ms 58196 KiB
17 Elfogadva 252ms 77268 KiB
18 Elfogadva 544ms 113320 KiB
19 Elfogadva 514ms 113204 KiB
20 Elfogadva 510ms 113356 KiB
subtask4 14/14
21 Elfogadva 3ms 50812 KiB
22 Elfogadva 2ms 50904 KiB
23 Elfogadva 2ms 50804 KiB
24 Elfogadva 2ms 50812 KiB
subtask5 20/20
25 Elfogadva 3ms 50824 KiB
26 Elfogadva 4ms 51040 KiB
27 Elfogadva 4ms 51036 KiB
28 Elfogadva 4ms 51044 KiB
29 Elfogadva 4ms 51040 KiB
30 Elfogadva 4ms 51036 KiB
31 Elfogadva 4ms 51048 KiB
32 Elfogadva 4ms 51048 KiB
subtask6 0/50
33 Elfogadva 8ms 51536 KiB
34 Elfogadva 68ms 58588 KiB
35 Elfogadva 497ms 98008 KiB
36 Elfogadva 507ms 98008 KiB
37 Elfogadva 578ms 113260 KiB
38 Elfogadva 662ms 113268 KiB
39 Időlimit túllépés 5.065s 81540 KiB
40 Időlimit túllépés 5.076s 81504 KiB
41 Elfogadva 517ms 100940 KiB