Submission #975239

#	Time	Username	Problem	Language	Result	Execution time	Memory
975239		yoav_s	Road Closures (APIO21_roads)	C++17	0 / 100	54 ms	18396 KiB

roads

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

#include "roads.h"


std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vvp graph(N);
    for (ll i = 0; i < N - 1; i++)
    {
        graph[U[i]].eb(V[i],W[i]);
        graph[V[i]].eb(U[i],W[i]);
    }

    v dfsOrder;
    v parent(N);
    stack<p> dfs;
    dfs.emplace(0, -1);
    vb visited(N, false);
    while (!dfs.empty())
    {
        auto top = dfs.top();
        dfs.pop();
        if (visited[top.f]) continue;
        visited[top.f] = true;
        dfsOrder.pb(top.f);
        parent[top.f] = top.s;
        for (auto x : graph[top.f]) dfs.emplace(x.f, top.f);
    }

    vv changing(N);
    for (ll i : dfsOrder)
    {
        for (ll j = 0; j < graph[i].size(); j++) changing[j].pb(i);
    }

    v freeForChildren(N, 0);
    vector<long long> res(N, 0);
    vb usedParent(N, false); usedParent[0] = true;
    ll sum = 0;
    for (ll i = N - 1; i >= 0; i--)
    {
        for (ll x : changing[i])
        {
            if (!usedParent[x] && freeForChildren[parent[x]] > 0)
            {
                freeForChildren[parent[x]]--;
                usedParent[x] = true;
            }
            else
            {
                sum++;
                freeForChildren[x]++;
            }
        }
        res[i] = sum;
    }
    return res;
}

/*
int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> U(N - 1), V(N - 1), W(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
  for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
    if (i > 0) {
      printf(" ");
    }
    printf("%lld",closure_costs[i]);
  }
  printf("\n");
  return 0;
}
/**/

Compilation message (stderr)

roads.cpp:107:1: warning: "/*" within comment [-Wcomment]
  107 | /**/
      |  
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:60:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (ll j = 0; j < graph[i].size(); j++) changing[j].pb(i);
      |                        ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22