oj.uz

Submission #414865

# Submission time Handle Problem Language Result Execution time Memory
414865 2021-05-31T09:47:12 Z JediMaster11 Traffic (IOI10_traffic) C++17
0 / 100
 1 ms 204 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -