QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#165686 | #6561. Fail Fast | PhantomThreshold# | WA | 2ms | 12584kb | C++20 | 1.4kb | 2023-09-05 20:47:30 | 2023-09-05 20:47:31 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
//define int long long
using namespace std;
const int maxn = 210000;
int par[maxn],fa[maxn];
int findfa(const int x){ return fa[x]==x?x:fa[x]=findfa(fa[x]); }
struct node
{
int i,id;
double p,t;
friend inline bool operator <(const node &k1,const node &k2)
{
return k1.t/k1.p > k2.t/k2.p;
}
}a[maxn];
int id[maxn],cnt;
int n, vis[maxn];
priority_queue< node > q;
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > >Q;
vector<int>V[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
a[0].p=1; a[0].t=0;
for(int i=1;i<=n;i++)
{
cin>>a[i].t>>a[i].p;
a[i].p= 1-a[i].p;
int x; cin>>x; par[i]=x;
V[x].push_back(i);
}
for(int i=0;i<=n;i++) fa[i]=i;
cnt=n;
for(int i=1;i<=n;i++)
{
id[i]=i;
a[i].i=i;
a[i].id=i;
q.push(a[i]);
}
int ord=0;
while(!q.empty())
{
const node temp= q.top(); q.pop();
int i=temp.i;
if( id[i]!=temp.id ) continue;
int j=findfa(par[i]);
a[j].t= a[j].t+ (1-a[j].p)*a[i].t;
a[j].p= 1- (1-a[j].p)*(1-a[i].p);
id[j]=a[j].id=++cnt;
if(par[j]) q.push( a[j] );
fa[i]=j;
vis[i]=++ord;
}
for(int i=1;i<=n;i++) if(par[i]==0)
Q.emplace( vis[i],i );
while(!Q.empty())
{
const auto [vs,i] = Q.top(); Q.pop();
cout<<i<<'\n';
for(auto j:V[i])
Q.emplace( vis[j],j );
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 12584kb
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: 10904kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
1 3 2 4
result:
wrong answer your plan is not optimal