QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#187904 | #6561. Fail Fast | Feet_McYeet | TL | 4ms | 10776kb | C++20 | 3.6kb | 2023-09-25 05:33:06 | 2023-09-25 05:33:06 |
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-n1.p) > n2.c/(1-n2.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);
cout.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) {
// cout << i spc << re[i].c spc << re[i].p el;
// }
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 (re[pa] < temp) {
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);
}
// forn(i,n) {
// cout << i spc << re[i].c/(1-re[i].p) el;
// }
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10776kb
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: 0ms
memory: 10692kb
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: 0
Accepted
time: 3ms
memory: 10616kb
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 5 7 1 10 8 9
result:
ok correct
Test #4:
score: 0
Accepted
time: 3ms
memory: 10664kb
input:
20 93 0.093030 0 53 0.056639 0 39 0.021549 0 48 0.069268 3 58 0.009572 4 22 0.015083 1 27 0.024351 5 68 0.085055 7 48 0.031563 5 46 0.025067 9 15 0.095445 2 57 0.011233 6 97 0.028239 2 8 0.060758 6 59 0.097330 13 34 0.052120 3 73 0.055127 11 53 0.004135 12 24 0.051183 5 56 0.027001 13
output:
3 16 4 2 11 5 19 7 9 10 8 17 1 6 14 12 18 13 20 15
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 10744kb
input:
20 971329 0.076234 0 996879 0.012978 0 994191 0.056803 0 978400 0.080792 1 907508 0.008858 4 992071 0.057419 2 901661 0.089621 6 912521 0.051943 5 979169 0.040201 5 904759 0.083405 7 928478 0.092658 7 980034 0.054747 3 906344 0.053231 10 907474 0.090196 8 927695 0.023153 4 995464 0.009387 2 984650 0...
output:
2 16 6 7 10 13 19 20 17 11 1 4 5 8 14 18 9 15 3 12
result:
ok correct
Test #6:
score: 0
Accepted
time: 3ms
memory: 10620kb
input:
20 54 0.952741 0 41 0.912397 0 11 0.963309 0 66 0.915806 3 47 0.919191 4 51 0.906473 5 24 0.989650 6 97 0.964070 7 56 0.997215 1 39 0.981950 2 50 0.994037 2 92 0.942000 7 97 0.900405 3 53 0.950071 6 16 0.980631 14 63 0.950876 10 49 0.995183 15 20 0.908520 5 71 0.949757 16 76 0.972330 9
output:
3 2 4 5 18 6 13 14 15 1 10 16 19 7 12 8 9 20 11 17
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 10692kb
input:
20 933154 0.904059 0 929160 0.911627 0 999437 0.921760 0 991335 0.904136 1 903530 0.943148 4 904464 0.921035 2 944382 0.912394 6 990971 0.982189 7 941308 0.959290 4 993916 0.945081 7 924496 0.989350 1 938782 0.958578 4 964442 0.997198 11 964358 0.938647 10 911972 0.943888 5 975140 0.993873 4 995611 ...
output:
1 4 2 6 7 3 5 15 10 14 20 12 19 9 11 13 17 8 18 16
result:
ok correct
Test #8:
score: 0
Accepted
time: 4ms
memory: 10676kb
input:
1 10 0.5 0
output:
1
result:
ok correct
Test #9:
score: 0
Accepted
time: 3ms
memory: 10772kb
input:
2 100 0.8 0 200 0.7 0
output:
1 2
result:
ok correct
Test #10:
score: 0
Accepted
time: 3ms
memory: 10644kb
input:
2 10 0.5 0 5 0.4 1
output:
1 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 10616kb
input:
2 1000 0.7 2 1 0.6 0
output:
2 1
result:
ok correct
Test #12:
score: -100
Time Limit Exceeded
input:
100000 938188 0.740681 0 575610 0.965656 1 937341 0.842524 2 817797 0.945396 3 602563 0.818956 4 893939 0.900203 5 952148 0.810399 6 538333 0.960769 7 550079 0.908188 8 676338 0.795726 9 546675 0.529045 10 542108 0.581119 11 963201 0.665127 12 564484 0.897025 13 504952 0.844118 14 673675 0.777947 15...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...