QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112288 | #6561. Fail Fast | ITMO_pengzoo# | WA | 2ms | 3628kb | C++20 | 2.5kb | 2023-06-11 03:04:37 | 2023-06-11 03:04:39 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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