#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
vector<vector<int>> E(N);
for (int i = 0; i < N - 1; i++){
int X, Y;
cin >> X >> Y;
X--;
Y--;
E[X].push_back(Y);
E[Y].push_back(X);
}
int M;
cin >> M;
vector<int> A(M), B(M), C(M);
for (int i = 0; i < M; i++){
cin >> A[i] >> B[i] >> C[i];
A[i]--;
B[i]--;
}
vector<int> S(N, 0);
for (int i = 0; i < M; i++){
vector<int> p(N, -1);
queue<int> Q;
Q.push(A[i]);
while (!Q.empty()){
int v = Q.front();
Q.pop();
for (int w : E[v]){
if (w != p[v]){
p[w] = v;
Q.push(w);
}
}
}
int v = B[i];
while (true){
S[v] |= 1 << i;
if (v == A[i]){
break;
}
v = p[v];
}
}
vector<vector<bool>> ok(M, vector<bool>(M, true));
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
for (int k = j + 1; k < M; k++){
if ((S[i] >> j & 1) == 1 && (S[i] >> k & 1) == 1){
ok[j][k] = false;
}
}
}
}
int ans = 0;
for (int i = 0; i < (1 << M); i++){
bool ok2 = true;
for (int j = 0; j < M; j++){
for (int k = j + 1; k < M; k++){
if ((i >> j & 1) == 1 && (i >> k & 1) == 1 && !ok[j][k]){
ok2 = false;
}
}
}
if (ok2){
int sum = 0;
for (int j = 0; j < M; j++){
if ((i >> j & 1) == 1){
sum += C[j];
}
}
ans = max(ans, sum);
}
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
340 KB |
Output is correct |
5 |
Correct |
203 ms |
7960 KB |
Output is correct |
6 |
Correct |
100 ms |
7608 KB |
Output is correct |
7 |
Correct |
119 ms |
7644 KB |
Output is correct |
8 |
Correct |
102 ms |
8432 KB |
Output is correct |
9 |
Correct |
129 ms |
7708 KB |
Output is correct |
10 |
Correct |
117 ms |
8476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1088 ms |
7968 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
340 KB |
Output is correct |
5 |
Correct |
203 ms |
7960 KB |
Output is correct |
6 |
Correct |
100 ms |
7608 KB |
Output is correct |
7 |
Correct |
119 ms |
7644 KB |
Output is correct |
8 |
Correct |
102 ms |
8432 KB |
Output is correct |
9 |
Correct |
129 ms |
7708 KB |
Output is correct |
10 |
Correct |
117 ms |
8476 KB |
Output is correct |
11 |
Incorrect |
654 ms |
552 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
340 KB |
Output is correct |
5 |
Correct |
203 ms |
7960 KB |
Output is correct |
6 |
Correct |
100 ms |
7608 KB |
Output is correct |
7 |
Correct |
119 ms |
7644 KB |
Output is correct |
8 |
Correct |
102 ms |
8432 KB |
Output is correct |
9 |
Correct |
129 ms |
7708 KB |
Output is correct |
10 |
Correct |
117 ms |
8476 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |