| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 536514 |
2022-03-13T13:17:11 Z |
Asymmetry |
Chase (CEOI17_chase) |
C++17 |
|
4000 ms |
14148 KB |
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
struct par {
long long x;
int y;
friend bool operator < (par p, par q) {
return p.y < q.y || (p.y == q.y && p.x < q.x);
}
};
struct info {
par on, off;
};
const int N = 101'000;
int n, m, a, b, kara;
int t[N];
int pr[N];
long long sum[N];
vector<int> v[N];
par ret;
par dp[N]; // zakładamy, że zaczynamy w X
void dfd(int x) {
for (int i : v[x]) {
if (i == pr[x]) {
continue;
}
pr[i] = x;
dfd(i);
}
}
void dfs(int x) {
dp[x] = {0, 0};
for (int i : v[x]) {
if (i == pr[x]) {
continue;
}
dfs(i);
dp[x] = max(dp[x], dp[i]);
}
if (sum[x] >= kara) {
dp[x].x += sum[x] - t[pr[x]] - kara;
++dp[x].y;
}
}
par check(int x) {
kara = x;
ret.x = -1e18;
ret.y = 0;
for (int i = 1; i <= n; ++i) {
pr[i] = 0;
dfd(i);
dfs(i);
ret = max(ret, dp[i]);
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
long long mx = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &t[i]);
}
for (int i = 1; i < n; ++i) {
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
dfd(1);
for (int i = 1; i <= n; ++i) {
for (int j : v[i]) {
sum[i] += t[j];
}
mx = max(mx, sum[i]);
}
long long bp = 0, bk = mx, bs;
while (bk - bp > 1) {
bs = (bp + bk) / 2;
par w = check(bs);
if (w.y >= m) {
bp = bs;
}
else {
bk = bs;
}
}
par w = check(bp);
printf("%lld\n", w.x + (long long)bp * m);
return 0;
}
Compilation message
chase.cpp: In function 'int main()':
chase.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d", &t[i]);
| ~~~~~^~~~~~~~~~~~~
chase.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4057 ms |
14148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
