27502023-01-20 18:58:18CattVarázserdőcpp17Accepted 100/1002.265s205284 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;

int main() {
    ll n,m;
    cin >> n >> m;

    vector<pair<ll, pair<ll, ll>> > g(m);
    for(ll i = 0; i < m; i++) {
        ll x,y,z;
        cin >> x >> y >> z;
        g[i] = {z, {x, y}};
    }

    vector<map<ll, ll> > v(n+1);
    ll mo = 0;

    sort(g.begin(), g.end());
    for(ll i = 0; i < m; i++) {
        ll x,y,z;
        z = g[i].first, x = g[i].second.first, y = g[i].second.second;
        mo += v[x][z-1] + v[y][z-1] + 2;
        mo %= MOD;
        v[x][z] += v[y][z-1] + 1;
        v[x][z] %= MOD;
        v[y][z] += v[x][z-1] + 1;
        v[y][z] %= MOD;
    }

    cout << (mo + MOD - m) % MOD;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms356 KiB
2Accepted3ms400 KiB
3Accepted3ms532 KiB
subtask27/7
4Accepted3ms744 KiB
5Accepted4ms612 KiB
6Accepted16ms3100 KiB
7Accepted17ms3700 KiB
8Accepted1.046s165756 KiB
9Accepted1.146s156992 KiB
10Accepted930ms147656 KiB
11Accepted1s141028 KiB
12Accepted855ms138144 KiB
13Accepted947ms138084 KiB
subtask39/9
14Accepted3ms888 KiB
15Accepted4ms896 KiB
16Accepted159ms24128 KiB
17Accepted690ms48196 KiB
18Accepted1.985s166960 KiB
19Accepted1.271s126536 KiB
20Accepted1.386s129764 KiB
subtask414/14
21Accepted3ms632 KiB
22Accepted3ms504 KiB
23Accepted3ms356 KiB
24Accepted3ms356 KiB
subtask520/20
25Accepted4ms876 KiB
26Accepted9ms1784 KiB
27Accepted8ms1272 KiB
28Accepted9ms1648 KiB
29Accepted9ms1636 KiB
30Accepted9ms1636 KiB
31Accepted8ms1124 KiB
32Accepted8ms1272 KiB
subtask650/50
33Accepted18ms3564 KiB
34Accepted246ms32228 KiB
35Accepted1.126s42788 KiB
36Accepted1.167s45376 KiB
37Accepted1.631s167140 KiB
38Accepted2.134s184548 KiB
39Accepted2.265s205284 KiB
40Accepted1.784s189028 KiB
41Accepted1.57s89700 KiB