QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187902#6561. Fail FastFeet_McYeetTL 2ms12828kbC++203.6kb2023-09-25 05:23:332023-09-25 05:23:34

Judging History

你现在查看的是最新测评结果

  • [2023-09-25 05:23:34]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:12828kb
  • [2023-09-25 05:23:33]
  • 提交

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);
    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/(1-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: 12516kb

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: 2ms
memory: 12020kb

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: 2ms
memory: 12828kb

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: 2ms
memory: 12004kb

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: 2ms
memory: 12168kb

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: 0ms
memory: 12612kb

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: 2ms
memory: 12168kb

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: 0ms
memory: 11880kb

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

score: 0
Accepted
time: 2ms
memory: 11944kb

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

score: 0
Accepted
time: 2ms
memory: 12016kb

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

score: 0
Accepted
time: 2ms
memory: 12552kb

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
...

result: