Submission #1162977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162977		avighna	Lost Array (NOI19_lostarray)	C++20	100 / 100	53 ms	13892 KiB

lostarray

#include <bits/stdc++.h>

typedef long long ll;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, m;
  std::cin >> n >> m;
  std::vector<std::set<std::pair<ll, ll>>> adj(n + 1);
  for (ll i = 0, a, b, c; i < m; ++i) {
    std::cin >> a >> b >> c;
    adj[a].insert({c, b});
    adj[b].insert({c, a});
  }

  std::vector<ll> ans(n + 1, 1);
  auto remove = [&](ll x) {
    for (auto &[wt, i] : adj[x]) {
      ans[i] = std::max(ans[i], wt);
      adj[i].erase({wt, x});
    }
    adj[x].clear();
  };
  for (ll i = 1; i <= n; ++i) {
    while (!adj[i].empty() and
           adj[i].begin()->first != (--adj[i].end())->first) {
      auto it1 = adj[i].begin();
      auto it2 = --adj[i].end();
      if (it1->first < it2->first) {
        ans[it1->second] = it1->first;
        remove(it1->second);
      } else {
        ans[it2->second] = it2->first;
        remove(it2->second);
      }
    }
  }

  for (ll i = 1; i <= n; ++i) {
    if (!adj[i].empty()) {
      ll a = i, b = adj[i].begin()->second;
      ll x = adj[i].begin()->first;
      // min(a, b) = x, and we should increase ans[idx]
      if (ans[a] >= x and ans[b] <= x) {
        ans[b] = x;
      } else {
        ans[a] = x;
      }
    }
  }

  for (ll i = 1; i <= n; ++i) {
    std::cout << ans[i] << ' ';
  }
  std::cout << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 48 / 48