Submission #414865

#	Time	Username	Problem	Language	Result	Execution time	Memory
414865		JediMaster11	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	204 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;
int smallPlace = 0;

ll recur(int 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]);
    }

    int 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;
}

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