QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#516966 | #6561. Fail Fast | ucup-team2307# | WA | 2ms | 11984kb | C++20 | 2.8kb | 2024-08-13 02:07:18 | 2024-08-13 02:07:19 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;
#define int ll
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
int n;
double c[100500];
double p[100500];
vector<int> g[100500];
double val[100500];
double mx[100500];
int pr[100500];
void dfs(int v, double ccur, double pcur)
{
if (v > 0)
val[v] = pcur / ccur;
else
val[v] = 1e18;
mx[v] = val[v];
for (int i : g[v])
{
pr[i] = v;
dfs(i, ccur+c[i]*(1-pcur), pcur+p[i]-pcur*p[i]);
mx[v] = max(mx[v], mx[i]);
}
}
int m = 1;
double c2[100500];
double p2[100500];
int dn[100500];
int id[100500];
vector<int> to[100500];
vector<int> g2[100500];
void dfs2(int v, int u)
{
id[v] = u;
int down = -1;
for (int i : g[v])
{
if (mx[i] == mx[v] && down == -1)
{
down = i;
dfs2(i, u);
}
}
if (down == -1)
{
dn[u] = v;
}
for (int i : g[v])
if (i!=down)
{
int q = m++;
g2[u].pb(q);
dfs2(i, q);
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for (int i=1; i<=n; i++)
{
int x;
cin>>c[i]>>p[i]>>x;
g[x].pb(i);
}
dfs(0, 0, 0);
pr[0] = -1;
dfs2(0, 0);
for (int i=0; i<m; i++)
{
to[i].clear();
int v = dn[i];
while (true)
{
to[i].pb(v);
v = pr[v];
if (v < 0 || id[v] != i)
break;
}
reverse(to[i].begin(), to[i].end());
int r = to[i].size();
double ccur = c[to[i][r-1]];
double pcur = p[to[i][r-1]];
for (int j=r-2; j>=0; j--)
{
int v = to[i][j];
ccur = c[v] + ccur*(1-p[v]);
pcur = pcur + p[v] - pcur*p[v];
}
c2[i] = ccur;
p2[i] = pcur;
}
// for (int i=0; i<m; i++)
// {
// cout<<i<<" : {";
// for (int j : to[i])
// cout<<j<<", ";
// cout<<"} -> ";
// for (int j : g2[i])
// cout<<j<<", ";
// cout<<"\n";
// }
vector<int> ans;
set<pair<double, int> > st;
for (int i : g2[0])
st.insert({p2[i] / c2[i], i});
while (!st.empty())
{
auto it = prev(st.end());
int v = it->se;
st.erase(it);
for (int i : to[v])
ans.pb(i);
for (int i : g2[v])
st.insert({p2[i] / c2[i], i});
}
for (int i : ans)
cout<<i<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11984kb
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: -100
Wrong Answer
time: 2ms
memory: 11956kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
1 3 4 2
result:
wrong answer your plan is not optimal