44992023-03-29 10:54:05AGergoLogisztikai központcpp17Wrong answer 1/5059ms128756 KiB
#include <bits/stdc++.h>

using namespace std;

//csak 1 út minden vársoba!
//jó város mindig a leghosszabb úton

vector<vector<int>> tav;
vector<vector<int>> gyerek;
vector<vector<int>> eljut;
int maxlen = 0, maxid;

void leghossz(int start,int cur, int dis)
    {
        for(int x : gyerek[cur])
        {
            if(tav[start][x] == -1)
            {
                tav[start][x] = dis + tav[cur][x];
                leghossz(start,x,dis + tav[cur][x]);
            }
        }
    }

    void leghosszut(int start,int cur, int dis, vector<int> jut)
    {
        for(int x : gyerek[cur])
        {
            if(tav[start][x] == -1)
            {
                tav[start][x] = dis + tav[cur][x];

                eljut[x] = jut;
                eljut[x].push_back(cur);

                leghosszut(start,x,dis + tav[cur][x],eljut[x]);
            }
        }
    }



int main()
{
    int varosszam;
    cin >> varosszam;

    int a,b;

    tav.resize(varosszam+1,vector<int>(varosszam+1,-1));
    gyerek.resize(varosszam+1);
    eljut.resize(varosszam+1);

    for(int i = 1; i < varosszam;i++)
    {
        tav[i][i] = 0;

        cin >> a >> b;

        cin >> tav[a][b];
        tav[b][a] = tav[a][b];

        gyerek[a].push_back(b);
        gyerek[b].push_back(a);
    }

    for(int x : gyerek[1])
    {
        leghossz(1,x,tav[1][x]);
    }

    for(int i = 1; i < varosszam+1;i++)
    {
        if(tav[1][i] > maxlen)
        {
            maxlen = tav[1][i];
            maxid = i;
        }
    }

    int v = maxid;

    for(int x : gyerek[v])
    {
        leghosszut(v,x,tav[v][x],{});
    }

    for(int i = 1; i < varosszam+1;i++)
    {
        if(tav[v][i] > maxlen)
        {
            maxlen = tav[v][i];
            maxid = i;
        }
    }

    int shortest;
    vector<int> longests;

    for(int x : eljut[maxid])
    {
        if(tav[v][x] > maxlen - tav[v][x] && tav[v][x] <= shortest)
        {
            if(tav[v][x] < shortest)
            {
                longests.clear();
            }
            shortest = tav[v][x];
            longests.push_back(x);
        }
        else if(tav[v][x] < maxlen - tav[v][x] && maxlen - tav[v][x] <= shortest)
        {
            if(maxlen - tav[v][x] < shortest)
            {
                longests.clear();
            }
            shortest = maxlen - tav[v][x];
            longests.push_back(x);
        }
    }

    cout << shortest << "\n" << longests.size() << "\n";
    for(int x : longests)
    {
        cout << x << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
base1/50
1Wrong answer0/03ms2088 KiB
2Runtime error0/052ms128756 KiB
3Wrong answer0/43ms2252 KiB
4Wrong answer0/43ms2448 KiB
5Wrong answer0/43ms2692 KiB
6Wrong answer0/43ms2752 KiB
7Wrong answer0/43ms3092 KiB
8Wrong answer0/57ms12528 KiB
9Runtime error0/250ms127552 KiB
10Runtime error0/250ms127520 KiB
11Wrong answer0/24ms5728 KiB
12Partially correct1/210ms21704 KiB
13Runtime error0/259ms127100 KiB
14Runtime error0/250ms126848 KiB
15Runtime error0/257ms126604 KiB
16Runtime error0/256ms126576 KiB
17Runtime error0/254ms126556 KiB
18Runtime error0/248ms126544 KiB
19Runtime error0/248ms126524 KiB
20Runtime error0/348ms126496 KiB