QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112286#6561. Fail FastITMO_pengzoo#WA 2ms3756kbC++202.5kb2023-06-11 03:02:342023-06-11 03:02: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:02:39]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3756kb
  • [2023-06-11 03:02:34]
  • 提交

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<int> 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] = 1 - pr;
    par[i] = d - 1;
    if (par[i] < 0) {
      par[i] = n;
    }
  }
  par[n] = -1;
  w[n] = 0.5;
  p[n] = 1;
  n++;
  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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3688kb

input:

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

output:

4
1
2
3

result:

ok correct

Test #2:

score: 0
Accepted
time: 2ms
memory: 3592kb

input:

4
84 0.716 0
91 0.115 0
19 0.640 1
103 0.455 0

output:

2
1
3
4

result:

ok correct

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3756kb

input:

10
18 0.574073 0
13 0.540309 0
13 0.539018 2
12 0.572910 2
15 0.570616 4
16 0.510215 3
17 0.504083 5
19 0.539297 1
19 0.577271 7
10 0.578346 1

output:

2
4
3
6
1
10
5
7
8
9

result:

wrong answer your plan is not optimal