Submission #414863

#	Time	Username	Problem	Language	Result	Execution time	Memory
414863		JediMaster11	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	208 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define endl "\n"
#define elif else if
#define fo(i, a, b) for (int i = a; i < (int)b; i++)
#define rfo(i, a, b) for (int i = a - 1; i >= b; i--)
#define v(i) vector<i>
#define vll vector<long long>
#define vstr vector<string>
#define pairll pair<long long, long long>
#define vpairll vector<pair<long long, long long>>
#define print(x) cout << x << "\n"

#define pushall(x, n)                   \
    x.resize(n);                        \
    for (int zz = 0; zz < (int)n; zz++) \
    {                                   \
        cin >> x[zz];                   \
    }

vector<vector<ll>> roads;
int* fans;
ll smallestMax = LLONG_MAX;
ll smallPlace=0;

ll recur(ll on, ll prev, ll total)
{

    if(roads[on].size()==1 && prev!=-1)//at the end
    {

        return fans[on];
 
    }

    ll maxR=-1;
    ll sum=0;
    for(auto x : roads[on]){
        if(x != prev){
            ll tmp = recur(x, on, total+fans[on]);
            maxR = max(maxR, tmp);
            sum+=tmp;
        }
    }

if(max(maxR, total) < smallestMax){
    smallestMax = max(maxR, total);
    smallPlace=on;
}

    //should return the sum of all recurs I think, but the max should be used to find the smallestMax
    return sum+fans[on];


    //compare total to all the values of recur added together, looking for the smallest max



}


int LocateCentre (int num, int p[], int s[], int d[]){

fans = p;
    roads.resize(num);

    fo(i, 0, num - 1)
    {

        roads[s[i]].push_back(d[i]);
        roads[d[i]].push_back(s[i]);
    }

    ll on = 0;
    while (roads[on].size() > 1)
    {
        on++;
    } //gets the start to a point with only 1 road

    if(num==1){
        print(0);
        return 0;
    }elif(num==2){
        print((fans[0] > fans[1] ? 1 : 0));
        return 0;
    }


    recur(on, -1, 0);

    return smallPlace;



}

int man()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int p[] = {30,10,10,10,10};
    int s[] = {0,1,2,3};
    int d[] = {1,2,3,4};
    int ans = LocateCentre(5, p, s, d);
    print(ans);

    // ll num;
    // cin >> num;

    // pushall(fans, num);

    // roads.resize(num);

    // fo(i, 0, num - 1)
    // {
    //     ll n1, n2;

    //     cin >> n1 >> n2;

    //     roads[n1].push_back(n2);
    //     roads[n2].push_back(n1);
    // }

    // ll on = 0;
    // while (roads[on].size() > 1)
    // {
    //     on++;
    // } //gets the start to a point with only 1 road

    // if(num==1){
    //     print(0);
    //     return 0;
    // }elif(num==2){
    //     print((fans[0] > fans[1] ? 1 : 0));
    //     return 0;
    // }


    // recur(on, -1, 0);

    // print(smallPlace);

    //smallest max

    return 0;
}

// dont want it on a city with only 1 road, its better to chose cities with a bigger population, as that doesnt add to the congestion
// in geenral, the more roads the better (as congestion is split between multiple roads)

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25