QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#112288#6561. Fail FastITMO_pengzoo#WA 2ms3628kbC++202.5kb2023-06-11 03:04:372023-06-11 03:04:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-11 03:04:39]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3628kb
  • [2023-06-11 03:04:37]
  • 提交

answer

//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#ifdef GOLIKOV
  #include "/Users/golikovnik/contests/debug.h"
#else
  #define debug(...) ;
#endif

template <class A, class B>
bool smin(A& x, B&& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A& x, B&& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  using ld = long double;
  int n; cin >> n;
  vector<ld> p(n + 1);
  vector<ld> w(n + 1);
  vector<int> par(n + 1, -1);
  for (int i = 0; i < n; ++i) {
    int c;
    ld pr;
    int d;
    cin >> c >> pr >> d;
    p[i] = c;
    w[i] = pr;
    par[i] = d - 1;
    if (par[i] < 0) {
      par[i] = n;
    }
  }
  par[n] = -1;
  w[n] = 0.5;
  p[n] = 0.5;
  n++;
  for (int i = 0; i < n; ++i) {
    swap(p[i], w[i]);
  }
  auto ip = p;
  auto iw = w;
  int root = -1;
  for (int i = 0; i < n; ++i) if (par[i] < 0) root = i;
  assert(root >= 0);

  set<pair<ld, int>> st;
  for (int i = 0; i < n; ++i) if (i != root) {
    st.emplace(p[i] / w[i], i);
  }
  vector<deque<int>> order(n);
  for (int i = 0; i < n; ++i) order[i] = {i};

  vector<int> dsu(n);
  iota(dsu.begin(), dsu.end(), 0);
  auto find = [&](auto&& self, int v) -> int {
    return dsu[v] == v ? v : dsu[v] = self(self, dsu[v]); 
  };

  while (!st.empty()) {
    int v = st.begin()->second;
    st.erase(st.begin());

    assert(dsu[v] == v);
    int u = find(find, par[v]);

    if (order[v].size() < order[u].size()) {
      order[u].insert(order[u].end(), order[v].begin(), order[v].end());
    } else {
      order[v].insert(order[v].begin(), order[u].begin(), order[u].end());
      order[v].swap(order[u]);
    }

    if (u != root) {
      st.erase({p[u] / w[u], u});
      w[u] += w[v];
      p[u] += p[v];
      st.emplace(p[u] / w[u], u);
    }
  
    dsu[v] = u;
  }

  assert(dsu[root] == root);
  order[root].erase(order[root].begin());
  for (int v : order[root]) {
    cout << v + 1 << '\n';
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3628kb

input:

4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0

output:

1
2
3
4

result:

wrong answer your plan is not optimal