QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187908#6561. Fail FastFeet_McYeetWA 138ms37492kbC++203.8kb2023-09-25 05:47:012023-09-25 05:47:01

Judging History

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

  • [2023-09-25 05:47:01]
  • 评测
  • 测评结果:WA
  • 用时:138ms
  • 内存:37492kb
  • [2023-09-25 05:47:01]
  • 提交

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 {
    long double c;
    long 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;

bool v[MAXN];

void dfs2(int cn) {
    if (v[cn]) return;
    v[cn] = true;
    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]);
    // forn(i,n) if (sz(cm[i])) cout << i spc;
    // nl;
    // forn(i,n) if (!sz(cm[i])) cout << i spc;
    // nl;
    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: 11964kb

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: 12716kb

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: 12212kb

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

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: 11968kb

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: 12688kb

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: 14180kb

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

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 12920kb

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

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

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 14008kb

input:

2
1000 0.7 2
1 0.6 0

output:

2
1

result:

ok correct

Test #12:

score: 0
Accepted
time: 126ms
memory: 32084kb

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:

ok correct

Test #13:

score: 0
Accepted
time: 68ms
memory: 30572kb

input:

100000
501234 0.500516 0
501214 0.503354 1
501013 0.504058 2
502546 0.502962 3
500273 0.505433 4
500197 0.505874 5
505941 0.500204 6
500455 0.506393 7
506433 0.500626 8
503652 0.503861 9
500935 0.507151 10
501370 0.506725 11
502595 0.506236 12
503444 0.505698 13
501723 0.508031 14
505738 0.504150 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:

ok correct

Test #14:

score: 0
Accepted
time: 138ms
memory: 37492kb

input:

100000
768956 0.999996 0
686063 0.999982 1
817790 0.999964 2
897069 0.999958 3
940413 0.999956 4
879098 0.999957 5
687880 0.999964 6
663602 0.999959 7
816976 0.999944 8
572136 0.999958 9
653227 0.999946 10
972448 0.999914 11
836815 0.999920 12
617305 0.999941 13
934633 0.999903 14
757071 0.999917 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:

ok correct

Test #15:

score: 0
Accepted
time: 121ms
memory: 25280kb

input:

100000
686602 0.755750 0
606835 0.951986 0
713656 0.504635 0
609527 0.663061 0
752558 0.613758 0
997011 0.880758 0
905135 0.574450 0
732880 0.774286 0
573515 0.609711 0
899010 0.630653 0
664787 0.949029 0
649162 0.965284 0
582075 0.957310 0
939848 0.848816 0
743139 0.738017 0
577134 0.723893 0
91476...

output:

253
67
161
137
179
1001
287
255
3403
97013
304
33
428
135
212
344
237
110
234
35
149
2447
65686
7360
281
267
357
235
11969
10350
55117
23101
44394
90
345
32287
94695
21214
188
5602
3
12430
219
17907
55
71206
152
87789
70
305
9
90656
238
210
5552
72776
205
236
6216
1136
648
1276
7802
92691
249
2763
5...

result:

ok correct

Test #16:

score: -100
Wrong Answer
time: 120ms
memory: 25384kb

input:

100000
866461 0.563475 0
566909 0.892585 1
794999 0.608805 1
572103 0.501998 1
889513 0.669248 4
712553 0.620050 3
721255 0.898776 3
731219 0.870250 5
958886 0.933100 5
946557 0.758386 1
829823 0.901169 6
513249 0.679404 6
707379 0.965023 2
686267 0.691424 13
790432 0.772695 3
630098 0.867609 11
975...

output:

1
4
255
1463
17335
2114
14926
25657
17157
19416
25749
33301
67686
2
43930
34070
382
2754
5745
5840
61325
61426
70
4349
739
5234
10413
2679
10128
14274
79762
30407
92693
98817
35
1243
11751
49724
94468
28424
41338
220
4584
702
10034
40074
1056
32441
28243
3
6
12
9550
123
1113
15255
26543
1657
3838
31...

result:

wrong answer your plan is not optimal