QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278874#6561. Fail Fastucup-team191#WA 3ms14280kbC++141.6kb2023-12-07 21:47:002023-12-07 21:47:00

Judging History

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

  • [2023-12-07 21:47:00]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:14280kb
  • [2023-12-07 21:47:00]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <set>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long double ld;
typedef pair < ld, ld > pd;
typedef pair < ld, pd > pld;

const int N = 1e5 + 500;
const ld EPS = 1e-12;
const ld INF = 1e24;


set < pair < ld, int > > res[N];
vector < int > ch[N];

void mrg(int x, int y) {
	if((int)res[x].size() < (int)res[y].size())
		swap(res[x], res[y]);
	for(auto tmp : res[y]) res[x].insert(tmp);
}

ld dp_p[N], dp_E[N];
int par[N], n;

ld get_cost(ld E, ld p){
	return 1 - p < EPS ? INF : E / (1 - p);
}


void dfs(int x){
	for(int y : ch[x]) {
		dfs(y);
		res[x].insert({get_cost(dp_E[y], dp_p[y]), y});		
	}
	for(;!res[x].empty();) {
		int y = res[x].begin() -> Y;
		ld novi_E = dp_E[y];
		ld novi_p = dp_p[y];
		if(get_cost(dp_E[x], dp_p[x]) > get_cost(dp_E[x] + dp_p[x] * novi_E, dp_p[x] * novi_p)) {
			dp_E[x] += dp_p[x] * novi_E;
			dp_p[x] *= novi_p;
			mrg(x, y);
			res[x].erase(res[x].begin());
		} else {
			break;
		}
 	}
}

void solve() {
	set < pair < ld, int > > kandidati;
	for(int i = 1;i <= n;i++) {
		dfs(i);
		if(par[i] == 0) kandidati.insert({get_cost(dp_E[i], dp_p[i]), i});
	}
	for(;!kandidati.empty();) {
		int x = kandidati.begin() -> Y;
		printf("%d\n", x);
		kandidati.erase(kandidati.begin());
		for(int y : ch[x]) {
			kandidati.insert({get_cost(dp_E[y], dp_p[y]), y});	
		}
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) {
		scanf("%Lf%Lf%d", dp_E + i, dp_p + i, par + i);
		if(par[i]) ch[par[i]].PB(i);
	}
	solve();
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 14280kb

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

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

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

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

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: -100
Wrong Answer
time: 2ms
memory: 13296kb

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
4
5
18
2
6
14
15
13
1
10
16
19
7
12
8
9
20
11
17

result:

wrong answer your plan is not optimal