#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
vector<pair<int, ll>> graph[N];
bool visx[N];
ll lenghtX[N];
bool visy[N];
ll lenghtY[N];
void dfsX(int node){
visx[node] = true;
for(auto child: graph[node]){
if(!visx[child.first]){
lenghtX[child.first] = 1LL*child.second + 1LL*lenghtX[node];
dfsX(child.first);
}
}
return;
}
void dfsY(int node){
visy[node] = true;
for(auto child: graph[node]){
if(!visy[child.first]){
lenghtY[child.first] = 1LL*child.second + 1LL*lenghtY[node];
dfsY(child.first);
}
}
return;
}
int max_score(int n, int x, int y, ll k, std::vector<int> u,
std::vector<int> v, std::vector<int> w){
for(int i = 0; i<n-1; i++){
graph[u[i]].push_back({v[i], 1LL*w[i]});
graph[v[i]].push_back({u[i], 1LL*w[i]});
}
dfsX(x);
dfsY(y);
for(int i = 0; i<=n; i++){
visx[i] = 0;
visy[i] = 0;
}
multiset<pair<pair<ll, ll>, ll>> s;
s.insert({{0, x}, 1});
s.insert({{0, y}, 2});
ll sum = 0;
int cnt = 0;
while(s.size()>0){
auto it = s.begin();
int v = (*it).first.second;
ll wt = (*it).first.first;
int mark = (*it).second;
s.erase(it);
if(mark == 1 && visx[v] == 1) continue;
else if(mark == 2 && visy[v] == 1) continue;
sum+= wt;
//cout<<sum<<" "<<v<<" "<<wt<<"\n";
if(sum<= k) cnt+=1;
else break;
if(s.find({{lenghtX[v]+ lenghtY[v] - wt, v}, 3-mark}) != s.end()){
s.erase({{lenghtX[v]+ lenghtY[v] - wt, v}, 3-mark});
s.insert({{lenghtX[v]+ lenghtY[v] - 2*wt, v}, 3-mark});
}
if(mark == 1){
//if(visx[v]) continue;
visx[v] = true;
for(auto u: graph[v]){
//if(visx[u.first] == 0){
if(visy[u.first]) s.insert({{max(lenghtX[u.first], lenghtY[u.first]) - lenghtY[u.first], u.first}, 1});
else s.insert({{lenghtX[u.first], u.first}, 1});
//visx[u.first] = true;
//}
}
}
else{
//if(visy[v]) continue;
visy[v] = true;
for(auto u: graph[v]){
//if(visy[u.first] == 0){
if(visx[u.first]) s.insert({{max(lenghtX[u.first], lenghtY[u.first]) - lenghtX[u.first], u.first}, 2});
else s.insert({{lenghtY[u.first], u.first}, 2});
//visy[u.first] = true;
//}
}
}
// for(auto x: s){
// cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<"\n";
// }
// cout<<"\n";
}
for(int i = 0; i<=n; i++){
lenghtX[i] = 0;
lenghtY[i] = 0;
visx[i] = 0;
visy[i] = 0;
graph[i].clear();
}
return cnt;
}
// int main() {
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> N(Q), X(Q), Y(Q);
// std::vector<long long> K(Q);
// std::vector<std::vector<int>> U(Q), V(Q), W(Q);
// for (int q = 0; q < Q; q++) {
// assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
// U[q].resize(N[q] - 1);
// V[q].resize(N[q] - 1);
// W[q].resize(N[q] - 1);
// for (int i = 0; i < N[q] - 1; ++i) {
// assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
// }
// }
// fclose(stdin);
// std::vector<int> result(Q);
// for (int q = 0; q < Q; q++) {
// result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
// }
// for (int q = 0; q < Q; q++) {
// printf("%d\n", result[q]);
// }
// fclose(stdout);
// return 0;
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
103 ms |
28880 KB |
Output is correct |
2 |
Correct |
65 ms |
32596 KB |
Output is correct |
3 |
Correct |
33 ms |
10320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6236 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6248 KB |
Output is correct |
5 |
Correct |
1 ms |
6236 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Correct |
1 ms |
6236 KB |
Output is correct |
8 |
Correct |
1 ms |
6236 KB |
Output is correct |
9 |
Correct |
2 ms |
6236 KB |
Output is correct |
10 |
Correct |
1 ms |
6236 KB |
Output is correct |
11 |
Correct |
2 ms |
6236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6236 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6248 KB |
Output is correct |
5 |
Correct |
1 ms |
6236 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Correct |
1 ms |
6236 KB |
Output is correct |
8 |
Correct |
1 ms |
6236 KB |
Output is correct |
9 |
Correct |
2 ms |
6236 KB |
Output is correct |
10 |
Correct |
1 ms |
6236 KB |
Output is correct |
11 |
Correct |
2 ms |
6236 KB |
Output is correct |
12 |
Correct |
1 ms |
6320 KB |
Output is correct |
13 |
Correct |
2 ms |
6232 KB |
Output is correct |
14 |
Correct |
1 ms |
6344 KB |
Output is correct |
15 |
Correct |
2 ms |
6236 KB |
Output is correct |
16 |
Correct |
1 ms |
6236 KB |
Output is correct |
17 |
Correct |
2 ms |
6232 KB |
Output is correct |
18 |
Correct |
2 ms |
6232 KB |
Output is correct |
19 |
Correct |
2 ms |
6440 KB |
Output is correct |
20 |
Correct |
1 ms |
6492 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6492 KB |
Output is correct |
24 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6236 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6248 KB |
Output is correct |
5 |
Correct |
1 ms |
6236 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Correct |
1 ms |
6236 KB |
Output is correct |
8 |
Correct |
1 ms |
6236 KB |
Output is correct |
9 |
Correct |
2 ms |
6236 KB |
Output is correct |
10 |
Correct |
1 ms |
6236 KB |
Output is correct |
11 |
Correct |
2 ms |
6236 KB |
Output is correct |
12 |
Correct |
1 ms |
6320 KB |
Output is correct |
13 |
Correct |
2 ms |
6232 KB |
Output is correct |
14 |
Correct |
1 ms |
6344 KB |
Output is correct |
15 |
Correct |
2 ms |
6236 KB |
Output is correct |
16 |
Correct |
1 ms |
6236 KB |
Output is correct |
17 |
Correct |
2 ms |
6232 KB |
Output is correct |
18 |
Correct |
2 ms |
6232 KB |
Output is correct |
19 |
Correct |
2 ms |
6440 KB |
Output is correct |
20 |
Correct |
1 ms |
6492 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6492 KB |
Output is correct |
23 |
Correct |
2 ms |
6492 KB |
Output is correct |
24 |
Correct |
1 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6492 KB |
Output is correct |
26 |
Correct |
2 ms |
6700 KB |
Output is correct |
27 |
Correct |
2 ms |
6748 KB |
Output is correct |
28 |
Correct |
2 ms |
6748 KB |
Output is correct |
29 |
Correct |
2 ms |
6748 KB |
Output is correct |
30 |
Correct |
2 ms |
6748 KB |
Output is correct |
31 |
Correct |
2 ms |
6748 KB |
Output is correct |
32 |
Correct |
3 ms |
6748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6232 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6236 KB |
Output is correct |
5 |
Correct |
1 ms |
6248 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Incorrect |
2 ms |
6236 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6232 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6236 KB |
Output is correct |
5 |
Correct |
1 ms |
6248 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Correct |
1 ms |
6236 KB |
Output is correct |
8 |
Correct |
1 ms |
6236 KB |
Output is correct |
9 |
Correct |
1 ms |
6236 KB |
Output is correct |
10 |
Correct |
2 ms |
6236 KB |
Output is correct |
11 |
Correct |
1 ms |
6236 KB |
Output is correct |
12 |
Correct |
2 ms |
6236 KB |
Output is correct |
13 |
Correct |
1 ms |
6320 KB |
Output is correct |
14 |
Correct |
2 ms |
6232 KB |
Output is correct |
15 |
Correct |
1 ms |
6344 KB |
Output is correct |
16 |
Correct |
2 ms |
6236 KB |
Output is correct |
17 |
Correct |
1 ms |
6236 KB |
Output is correct |
18 |
Correct |
2 ms |
6232 KB |
Output is correct |
19 |
Incorrect |
2 ms |
6236 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6232 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6236 KB |
Output is correct |
5 |
Correct |
1 ms |
6248 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Correct |
1 ms |
6236 KB |
Output is correct |
8 |
Correct |
1 ms |
6236 KB |
Output is correct |
9 |
Correct |
1 ms |
6236 KB |
Output is correct |
10 |
Correct |
2 ms |
6236 KB |
Output is correct |
11 |
Correct |
1 ms |
6236 KB |
Output is correct |
12 |
Correct |
2 ms |
6236 KB |
Output is correct |
13 |
Correct |
1 ms |
6320 KB |
Output is correct |
14 |
Correct |
2 ms |
6232 KB |
Output is correct |
15 |
Correct |
1 ms |
6344 KB |
Output is correct |
16 |
Correct |
2 ms |
6236 KB |
Output is correct |
17 |
Correct |
1 ms |
6236 KB |
Output is correct |
18 |
Correct |
2 ms |
6232 KB |
Output is correct |
19 |
Correct |
2 ms |
6232 KB |
Output is correct |
20 |
Correct |
2 ms |
6440 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6492 KB |
Output is correct |
23 |
Correct |
1 ms |
6492 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6492 KB |
Output is correct |
26 |
Incorrect |
2 ms |
6236 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6232 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6236 KB |
Output is correct |
5 |
Correct |
1 ms |
6248 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Correct |
1 ms |
6236 KB |
Output is correct |
8 |
Correct |
1 ms |
6236 KB |
Output is correct |
9 |
Correct |
1 ms |
6236 KB |
Output is correct |
10 |
Correct |
2 ms |
6236 KB |
Output is correct |
11 |
Correct |
1 ms |
6236 KB |
Output is correct |
12 |
Correct |
2 ms |
6236 KB |
Output is correct |
13 |
Correct |
1 ms |
6320 KB |
Output is correct |
14 |
Correct |
2 ms |
6232 KB |
Output is correct |
15 |
Correct |
1 ms |
6344 KB |
Output is correct |
16 |
Correct |
2 ms |
6236 KB |
Output is correct |
17 |
Correct |
1 ms |
6236 KB |
Output is correct |
18 |
Correct |
2 ms |
6232 KB |
Output is correct |
19 |
Correct |
2 ms |
6232 KB |
Output is correct |
20 |
Correct |
2 ms |
6440 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6492 KB |
Output is correct |
23 |
Correct |
1 ms |
6492 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6492 KB |
Output is correct |
26 |
Correct |
3 ms |
6492 KB |
Output is correct |
27 |
Correct |
2 ms |
6700 KB |
Output is correct |
28 |
Correct |
2 ms |
6748 KB |
Output is correct |
29 |
Correct |
2 ms |
6748 KB |
Output is correct |
30 |
Correct |
2 ms |
6748 KB |
Output is correct |
31 |
Correct |
2 ms |
6748 KB |
Output is correct |
32 |
Correct |
2 ms |
6748 KB |
Output is correct |
33 |
Correct |
3 ms |
6748 KB |
Output is correct |
34 |
Incorrect |
2 ms |
6236 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
35 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6232 KB |
Output is correct |
2 |
Correct |
1 ms |
6232 KB |
Output is correct |
3 |
Correct |
1 ms |
6236 KB |
Output is correct |
4 |
Correct |
1 ms |
6236 KB |
Output is correct |
5 |
Correct |
1 ms |
6248 KB |
Output is correct |
6 |
Correct |
1 ms |
6236 KB |
Output is correct |
7 |
Correct |
1 ms |
6236 KB |
Output is correct |
8 |
Correct |
1 ms |
6236 KB |
Output is correct |
9 |
Correct |
1 ms |
6236 KB |
Output is correct |
10 |
Correct |
2 ms |
6236 KB |
Output is correct |
11 |
Correct |
1 ms |
6236 KB |
Output is correct |
12 |
Correct |
2 ms |
6236 KB |
Output is correct |
13 |
Correct |
1 ms |
6320 KB |
Output is correct |
14 |
Correct |
2 ms |
6232 KB |
Output is correct |
15 |
Correct |
1 ms |
6344 KB |
Output is correct |
16 |
Correct |
2 ms |
6236 KB |
Output is correct |
17 |
Correct |
1 ms |
6236 KB |
Output is correct |
18 |
Correct |
2 ms |
6232 KB |
Output is correct |
19 |
Correct |
2 ms |
6232 KB |
Output is correct |
20 |
Correct |
2 ms |
6440 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6492 KB |
Output is correct |
23 |
Correct |
1 ms |
6492 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6492 KB |
Output is correct |
26 |
Correct |
3 ms |
6492 KB |
Output is correct |
27 |
Correct |
2 ms |
6700 KB |
Output is correct |
28 |
Correct |
2 ms |
6748 KB |
Output is correct |
29 |
Correct |
2 ms |
6748 KB |
Output is correct |
30 |
Correct |
2 ms |
6748 KB |
Output is correct |
31 |
Correct |
2 ms |
6748 KB |
Output is correct |
32 |
Correct |
2 ms |
6748 KB |
Output is correct |
33 |
Correct |
3 ms |
6748 KB |
Output is correct |
34 |
Incorrect |
2 ms |
6236 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
35 |
Halted |
0 ms |
0 KB |
- |