10631 2024. 04. 07 14:24:23 111 Varázserdő cpp17 Hibás válasz 7/100 3.368s 504188 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<vector<pair<int,int>>>g(N+1);
	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.rbegin(),e.rend());
	for(int i=0;i<M;i++){
		auto[c,a,b]=e[i];
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}
	vector<int>v(N+1);
	vector<unordered_map<int,int>>w(N+1);
	auto dfs=[&](auto self,int i)->void{
		for(auto[j,c]:g[i]){
			if(v[j]){
				continue;
			}
			v[j]=v[i]+1;
			self(self,j);
			w[i][c]+=w[j][c+1]+1;
			w[i][c]%=MOD;
		}
	};
	v[1]=1;
	dfs(dfs,1);
	auto dfs2=[&](auto self,int i)->void{
		for(auto[j,c]:g[i]){
			if(v[j]){
				w[i][c]+=w[j][c+1]+1;
				w[i][c]%=MOD;
				continue;
			}
			v[j]=v[i]+1;
			self(self,j);
		}
	};
	fill(v.begin(),v.end(),0);
	v[1]=1;
	dfs2(dfs2,1);
	int ans=0;
	for(int i=1;i<=N;i++){
		for(auto[x,y]:w[i]){
			ans+=y;
			ans%=MOD;
		}
	}
	ans-=M;
	cout<<ans<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1892 KiB
2 Elfogadva 3ms 2088 KiB
3 Elfogadva 3ms 2304 KiB
subtask2 7/7
4 Elfogadva 3ms 2432 KiB
5 Elfogadva 4ms 3516 KiB
6 Elfogadva 17ms 11492 KiB
7 Elfogadva 17ms 12248 KiB
8 Elfogadva 1.263s 470488 KiB
9 Elfogadva 994ms 469444 KiB
10 Elfogadva 1.12s 467884 KiB
11 Elfogadva 865ms 469716 KiB
12 Elfogadva 975ms 475048 KiB
13 Elfogadva 964ms 477812 KiB
subtask3 0/9
14 Hibás válasz 3ms 49264 KiB
15 Hibás válasz 4ms 49920 KiB
16 Hibás válasz 83ms 82632 KiB
17 Hibás válasz 823ms 202528 KiB
18 Hibás válasz 3.368s 504188 KiB
19 Hibás válasz 1.656s 413636 KiB
20 Hibás válasz 1.634s 434424 KiB
subtask4 0/14
21 Hibás válasz 3ms 45220 KiB
22 Hibás válasz 3ms 45496 KiB
23 Hibás válasz 3ms 45364 KiB
24 Hibás válasz 3ms 45368 KiB
subtask5 0/20
25 Hibás válasz 4ms 46368 KiB
26 Hibás válasz 8ms 48280 KiB
27 Hibás válasz 8ms 47748 KiB
28 Hibás válasz 8ms 48580 KiB
29 Hibás válasz 8ms 48412 KiB
30 Hibás válasz 8ms 48264 KiB
31 Hibás válasz 8ms 48156 KiB
32 Hibás válasz 8ms 48048 KiB
subtask6 0/50
33 Hibás válasz 19ms 54032 KiB
34 Hibás válasz 79ms 79996 KiB
35 Hibás válasz 870ms 198796 KiB
36 Hibás válasz 879ms 243672 KiB
37 Hibás válasz 2.02s 475036 KiB
38 Hibás válasz 2.198s 485692 KiB
39 Hibás válasz 2.568s 501688 KiB
40 Hibás válasz 2.94s 495164 KiB
41 Hibás válasz 1.662s 284444 KiB