QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#517016#6561. Fail Fastucup-team2307#WA 133ms51316kbC++202.8kb2024-08-13 02:56:502024-08-13 02:56:50

Judging History

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

  • [2024-08-13 02:56:50]
  • 评测
  • 测评结果:WA
  • 用时:133ms
  • 内存:51316kb
  • [2024-08-13 02:56:50]
  • 提交

answer

#include <bits/stdc++.h>

typedef long long ll;
#define int ll

typedef long double ld;
#define double ld

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back

int n;
double c[100500];
double p[100500];
vector<int> g[100500];

struct Node
{
    double c;
    double p;
    int l;
    int r;
};
int m = 0;
Node t[200500];
struct Id
{
    int i;
};
bool operator < (Id x, Id y){ return tuple(t[x.i].p/t[x.i].c, t[x.i].l, t[x.i].r) > tuple(t[y.i].p/t[y.i].c, t[x.i].l, t[x.i].r); }
set<Id> st[200500];

void process(int v, int u)
{
//    cout<<v<<" "<<u<<" "<<st[v].size()<<"\n";
    while (st[v].size() > 0 && !(Id{u} < *st[v].begin()) )
    {
        auto vr = (*st[v].begin()).i;
        st[v].erase(st[v].begin());

        t[m].c = t[u].c + t[vr].c * (1-t[u].p);
        t[m].p = t[u].p + t[vr].p - t[u].p * t[vr].p;
        t[m].l = u;
        t[m].r = vr;
        u = m;
        m++;
    }
    st[v].insert(Id{u});
}

int dfs(int v)
{
//    cout<<v<<endl;
    if (g[v].empty())
    {
        t[m].c = c[v];
        t[m].p = p[v];
        t[m].l = -1;
        t[m].r = v;
        st[v].insert(Id{m});
        m++;

        return v;
    }

    vector<int> vec;
    for (int i : g[v])
        vec.pb(dfs(i));

    pair<int, int> mx = {-1, -1};
    for (int i : vec)
        if (int(g[i].size()) > mx.fi)
        {
            mx.fi = g[i].size();
            mx.se = i;
        }
    int u = mx.se;
    for (int i : vec)
        if (i!=u)
        {
            for (auto id : st[i])
                st[u].insert(id);
        }

    t[m].c = c[v];
    t[m].p = p[v];
    t[m].l = -1;
    t[m].r = v;
    m++;
    process(u, m-1);

//    cout<<v<<" -> ";
//    for (auto id : st[u])
//    {
//        int x = id.i;
//        cout<<t[x].c<<" "<<t[x].p<<" "<<t[x].l<<" "<<t[x].r<<", ";
//    }
//    cout<<"\n";
    return u;
}

vector<int> ans;
void Run(int v)
{
    if (t[v].l == -1)
    {
        ans.pb(t[v].r);
        return;
    }

    Run(t[v].l);
    Run(t[v].r);
}

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++)
    {
        int x;
        cin>>c[i]>>p[i]>>x;

//        c[i] = rand()%10+1;
//        p[i] = (rand()%10)/20.0+0.25;
//        x = rand()%i;

        p[i] = 1-p[i];
        g[x].pb(i);
    }
    c[0] = 1e18;
    p[0] = 1e-18;

    int r = dfs(0);

    for (auto id : st[r])
        Run(id.i);

//    cout<<st[r].size()<<"\n";
    for (int i : ans)
        if (i > 0)
            cout<<i<<"\n";
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 16740kb

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

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

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

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: 3ms
memory: 17548kb

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
17
19
20
11
1
4
5
15
8
14
18
9
3
12

result:

ok correct

Test #6:

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

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

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

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

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

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

score: 0
Accepted
time: 3ms
memory: 16756kb

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

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

input:

2
1000 0.7 2
1 0.6 0

output:

2
1

result:

ok correct

Test #12:

score: 0
Accepted
time: 62ms
memory: 47328kb

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: 96ms
memory: 51316kb

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: 53ms
memory: 47512kb

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: 125ms
memory: 44820kb

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: 0
Accepted
time: 133ms
memory: 48196kb

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
70
4349
739
5234
2679
10128
14274
10413
35
1243
11751
30407
49724
94468
92693
98817
28424
41338
79762
220
4584
702
10034
40074
1056
32441
2754
5745
5840
61325
61426
28243
3
6
12
9550
123
1113
15255
26543
1657
3838
31...

result:

ok correct

Test #17:

score: 0
Accepted
time: 127ms
memory: 43336kb

input:

100000
724633 0.992242 0
519908 0.739362 1
841119 0.933434 2
791058 0.900611 3
675619 0.998138 4
764793 0.750214 5
749590 0.659667 6
999818 0.893057 7
643755 0.894506 8
843096 0.848621 9
948647 0.664404 10
914991 0.753675 11
923272 0.619427 12
937334 0.894654 13
811519 0.627730 14
610149 0.981146 15...

output:

1
2
3534
1245
9813
18840
3255
17466
2329
5499
10237
28651
58928
63019
72223
3738
79615
1525
59464
8134
8727
390
71564
7842
10595
99232
89273
10764
35414
14731
20737
89154
14055
3552
69171
11710
17881
33462
11875
19460
22920
24318
14524
45990
7751
9761
8722
75995
3968
9240
65365
40991
80419
12494
262...

result:

ok correct

Test #18:

score: 0
Accepted
time: 95ms
memory: 41332kb

input:

100000
526633 0.902698 0
515821 0.957942 1
871718 0.810818 2
920847 0.633590 3
826181 0.806362 4
876673 0.742829 5
614618 0.612000 6
853505 0.831590 7
511485 0.830238 8
632217 0.794467 9
671254 0.883474 10
695783 0.701932 11
862825 0.611140 12
678224 0.856628 13
659493 0.947587 14
893183 0.970325 15...

output:

1
2
52258
3
4
5
6
7
8
9
10
63310
11
12
13
55535
70001
14
94065
87644
15
16
17
18
19
20
21
22
23
61227
24
25
26
27
54174
28
29
30
31
32
75852
69617
33
34
35
52672
95714
53846
36
60306
37
50265
38
39
63613
64784
82319
60688
40
41
42
43
80655
44
45
46
76567
47
48
49
50
76243
51
52
53
60308
54
55
56
57
...

result:

ok correct

Test #19:

score: -100
Wrong Answer
time: 0ms
memory: 18888kb

input:

100
456 0.123000 44
456 0.123000 0
456 0.123000 9
456 0.123000 10
456 0.123000 95
456 0.123000 100
456 0.123000 53
456 0.123000 37
456 0.123000 37
456 0.123000 42
456 0.123000 40
456 0.123000 4
456 0.123000 47
456 0.123000 4
456 0.123000 84
456 0.123000 71
456 0.123000 83
456 0.123000 2
456 0.123000...

output:

2
18
53
7
31
62
46
40
11
70
9
3
43

result:

wrong output format Unexpected end of file - int32 expected