Intermediate.
Put your skills to the test.

Problem summary

Each road between two distinct towns is paved half by each endpoint town. If its integer length is odd, the smaller-numbered town receives the extra kilometre. Find every town with the largest total contribution and that total.

Source clarification. The introductory prose says N < 10000, but the formal constraints allow N ≤ 100000. This implementation supports the larger bound.

Constraints

The constraints section states 2 ≤ N ≤ M ≤ 100000 and road length ≤ 500000. Towns are numbered 1..N; endpoints differ.

Worked example

Original statement sample.

5 8
1 3 8
4 1 5
4 5 19
2 4 11
3 2 18
1 5 10
5 3 9
2 1 4

3 5
18

Solution analysis

1. Keep a total for each town. A road of length length contributes floor(length/2) to both endpoints. If length is odd, add one more to the smaller endpoint.
2. After reading all roads, find the largest total. A second scan from town 1 to town N prints precisely the maximizing towns in the required increasing order. There is no need to store the roads.
3. In the sample the totals for towns 1 through 5 are 14, 17, 18, 15, and 18. Towns 3 and 5 therefore share the maximum of 18.

Why it works

For each even road the assigned halves sum to its length; for an odd road the extra unit goes to exactly the prescribed endpoint. Summing these independent contributions gives every town’s total. Scanning all totals then finds exactly all maxima.

Watch out. The extra kilometre depends on town numbers, not input endpoint order. A town total may exceed int; use long long. Print all ties, not only the first.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<long long>total(n+1,0);
    for(int road=0;road<m;road++){
        int u,v,length;
        cin>>u>>v>>length;
        total[u]+=length/2;
        total[v]+=length/2;
        // The lower town number takes the odd kilometre.
        total[min(u,v)]+=length%2;
    }
    long long maximum=*max_element(total.begin()+1,total.end());
    bool first=true;
    for(int town=1;town<=n;town++){
        if(total[town]==maximum){
            if(!first){
                cout<<' ';
            }
            cout<<town;
            first=false;
        }
    }
    cout<<'\n'<<maximum<<'\n';
}