QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#187898 | #6561. Fail Fast | Feet_McYeet | WA | 2ms | 10620kb | C++17 | 3.4kb | 2023-09-25 05:07:48 | 2023-09-25 05:07:49 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <iterator>
#include <algorithm>
// #include <bit>
#include <numeric>
#include <iomanip>
#include <stack>
using namespace std;
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#define el << '\n'
#define nl cout << '\n'
#define cina(a,n) for (int i=0; i<n; i++) cin >> a[i]
#define ll long long
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define ansyes cout << "YES\n"
#define ansno cout << "NO\n"
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pss pair<short, short>
#define MAX *max_element
#define MIN *min_element
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define bsi(x, v) (int) (lower_bound(x.begin(), x.end(), v) - x.begin());
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;
const int MAXN = 100005;
struct node {
double c;
double p;
int o;
};
bool operator < (const node& n1, const node& n2) {
return n1.c*(1-n2.p) > n2.c*(1-n1.p);
}
bool operator != (const node& n1, const node& n2) {
return !(n1.c==n2.c && n1.p==n2.p && n1.o==n2.o);
}
int par[MAXN];
int dep[MAXN];
void join(int a, int b) {
if (dep[a]>dep[b]) swap(a,b);
par[b] = a;
}
int g(int cn) {
if (par[cn] == cn) return cn;
par[cn] = g(par[cn]);
return par[cn];
}
int p[MAXN];
vector<int> ch[MAXN];
vector<int> cm[MAXN];
vector<int> cdm[MAXN];
void dfs(int cn, int d) {
dep[cn] = d;
for (int i : ch[cn]) dfs(i, d+1);
}
node re[MAXN];
priority_queue<node> pq;
void dfs2(int cn) {
cout << cn+1 el;
for (int i : cdm[cn]) {
pq.push(re[i]);
}
for (int i : cm[cn]) {
dfs2(i);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
forn(i,n) {
par[i] = i;
}
forn(i,n) {
cin >> re[i].c >> re[i].p >> p[i];
p[i]--;
re[i].o = i;
pq.push(re[i]);
if (p[i] != -1) ch[p[i]].pb(i);
}
forn(i,n) if (p[i]==-1) dfs(i, 0);
while (sz(pq)) {
// cout << sz(pq) << endl;
node temp = pq.top();
pq.pop();
if (re[temp.o] != temp) continue;
if (p[temp.o] == -1) continue;
int pa = g(p[temp.o]);
if (temp < re[pa]) {
re[pa].c += re[pa].p * temp.c;
re[pa].p *= temp.p;
cm[p[temp.o]].pb(temp.o);
pq.push(re[pa]);
join(pa, temp.o);
}
}
forn(i,n) {
vector<int> temp;
temp.rsz(sz(cm[i]));
forn(j,sz(cm[i])) temp[j] = cm[i][j];
sort(all(temp));
sort(all(ch[i]));
int a = 0, b = 0 ;
forn(k, sz(temp)+sz(ch[i])) {
if (b == sz(temp)) {
cdm[i].pb(ch[i][a]);
a++;
continue;
}
if (ch[i][a] == temp[b]) {
a++; b++; k++;
continue;
}
cdm[i].pb(ch[i][a]);
a++;
}
}
forn(i,n) if (p[i]==-1) pq.push(re[i]);
while (sz(pq)) {
int temp = pq.top().o;
pq.pop();
dfs2(temp);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10620kb
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: 0ms
memory: 10616kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
2 4 1 3
result:
wrong answer your plan is not optimal