Submission #99806

#	Time	Username	Problem	Language	Result	Execution time	Memory
99806		Alexa2001	Transport (COCI19_transport)	C++17	130 / 130	546 ms	36464 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 1e5 + 5;

int n, All, scade;
int w[Nmax], A[Nmax], label[Nmax];
bool used[Nmax];
ll need_up[Nmax], need_down[Nmax], cost[Nmax], fuel[Nmax];
ll answer;

vector<ll> valA[Nmax], valB[Nmax];
vector<int> v[Nmax], c[Nmax];


void dfs(int node, int dad = 0)
{
    w[node] = 1;
    for(auto it : v[node])
        if(it != dad && !used[it])
        {
            dfs(it, node);
            w[node] += w[it];
        }
}

pair<int,int> centroid(int node, int dad = 0)
{
    int up = All - w[node];
    pair<int,int> best = {All, node};

    for(auto it : v[node])
        if(it != dad && !used[it])
        {
            best = min(best, centroid(it, node));
            up = max(up, w[it]);
        }
    best = min(best, {up, node});
    return best;
}

void prec(int node, int dad)
{
    if(need_up[node] <= A[node])
        valA[label[node]].push_back(fuel[node] - cost[node]);

    valB[label[node]].push_back(need_down[node]);

    int x, cst, i;
    for(i=0; i<v[node].size(); ++i)
    {
        x = v[node][i];
        cst = c[node][i];
        if(used[x] || x == dad) continue;

        if(dad == 0) label[x] = i;
            else label[x] = label[node];

        fuel[x] = fuel[node] + A[x];
        cost[x] = cost[node] + cst;

        need_up[x] = max((ll)cst, need_up[node] + cst - A[node]);
        need_down[x] = max(need_down[node], cost[x] - (fuel[node] - scade));

        prec(x, node);
    }
}

ll calc(vector<ll> &a, vector<ll> &b) /// number of pairs such that elA >= elB
{
    int i = 0, j = 0;
    ll ans = 0;

    for(i=0; i<a.size(); ++i)
    {
        while(j<b.size() && a[i] >= b[j]) ++j;
        ans += j;
    }
    return ans;
}

void solve(int node)
{
    dfs(node);
    All = w[node];
    node = centroid(node).second;

    cost[node] = 0;
    fuel[node] = A[node];
    need_down[node] = need_up[node] = 0;
    label[node] = v[node].size();

    scade = A[node];
    prec(node, 0);

    vector<ll> VA, VB;

    int i;
    for(i=0; i<=v[node].size(); ++i)
        if(i == v[node].size() || !used[v[node][i]])
        {
            sort(valA[i].begin(), valA[i].end());
            sort(valB[i].begin(), valB[i].end());

            answer -= calc(valA[i], valB[i]);

            for(auto it : valA[i]) VA.push_back(it);
            for(auto it : valB[i]) VB.push_back(it);

            valA[i].clear(); valB[i].clear();
        }

    sort(VA.begin(), VA.end());
    sort(VB.begin(), VB.end());

    answer += calc(VA, VB);
  //  answer --;

    used[node] = 1;
    for(auto it : v[node])
        if(!used[it]) solve(it);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, x, y, cost;
    cin >> n;
    for(i=1; i<=n; ++i) cin >> A[i];

    for(i=1; i<n; ++i)
    {
        cin >> x >> y >> cost;
        v[x].push_back(y);
        v[y].push_back(x);
        c[x].push_back(cost);
        c[y].push_back(cost);
    }

    solve(1);
    cout << answer << '\n';

    return 0;
}

Compilation message (stderr)

transport.cpp: In function 'void prec(int, int)':
transport.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
transport.cpp: In function 'll calc(std::vector<long long int>&, std::vector<long long int>&)':
transport.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<a.size(); ++i)
              ~^~~~~~~~~
transport.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j<b.size() && a[i] >= b[j]) ++j;
               ~^~~~~~~~~
transport.cpp: In function 'void solve(int)':
transport.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<=v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~~
transport.cpp:102:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == v[node].size() || !used[v[node][i]])
            ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13