제출 #975244

#제출 시각아이디문제언어결과실행 시간메모리
975244yoav_s도로 폐쇄 (APIO21_roads)C++17
0 / 100
54 ms18188 KiB
#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); } reverse(all(dfsOrder)); vv changing(N); for (ll i : dfsOrder) { for (ll j = 0; j < graph[i].size(); j++) changing[j].pb(i); } //reverse dfs order, always direct to parent v freeFromChildren(N, 0); 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]) { bool childAvailable = false; if (freeFromChildren[x] > 0) freeFromChildren[x]--; else if (x != 0 && !usedParent[x]) { usedParent[x] = true; if (freeForChildren[parent[x]] > 0) freeForChildren[parent[x]]--; else { sum++; freeFromChildren[parent[x]]++; } } 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; } /**/

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp:114:1: warning: "/*" within comment [-Wcomment]
  114 | /**/
      |  
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);
      |                        ~~^~~~~~~~~~~~~~~~~
roads.cpp:71:18: warning: unused variable 'childAvailable' [-Wunused-variable]
   71 |             bool childAvailable = false;
      |                  ^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...