QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187919#6561. Fail FastFeet_McYeetWA 500ms44372kbC++203.9kb2023-09-25 06:11:392023-09-25 06:11:40

Judging History

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

  • [2023-09-25 06:11:40]
  • 评测
  • 测评结果:WA
  • 用时:500ms
  • 内存:44372kb
  • [2023-09-25 06:11:39]
  • 提交

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 {
    __float128 c;
    __float128 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);
    cout.tie(NULL);
    int n; cin >> n;
    forn(i,n) {
        par[i] = i;
    }
    forn(i,n) {
        long double t1, t2; cin >> t1 >> t2 >> p[i];
        re[i] = {t1, t2, i};
        p[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);
    bool v2[n];
    forn(i,n) v2[i] = false;
    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;
        if (v2[temp.o]) continue;
        v2[temp.o] = true;
        // cout << temp.o spc << temp.c spc << temp.p spc << re[temp.o].c spc << re[temp.o].p el;
        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);
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11776kb

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

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

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

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

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

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

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

input:

1
10 0.5 0

output:

1

result:

ok correct

Test #9:

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

input:

2
100 0.8 0
200 0.7 0

output:

1
2

result:

ok correct

Test #10:

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

input:

2
10 0.5 0
5 0.4 1

output:

1
2

result:

ok correct

Test #11:

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

input:

2
1000 0.7 2
1 0.6 0

output:

2
1

result:

ok correct

Test #12:

score: 0
Accepted
time: 488ms
memory: 37288kb

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: 194ms
memory: 30804kb

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: 500ms
memory: 44372kb

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: 482ms
memory: 25612kb

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: 464ms
memory: 24628kb

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