# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
48492 |
2018-05-14T19:06:37 Z |
WLZ |
Paprike (COI18_paprike) |
C++17 |
|
1000 ms |
14844 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
const int INF = 1e9;
const int MAXN = 1e5 + 5;
const ll LINF = 1e18;
const double pi = acos(-1);
const double EPS = 1e-9;
template <class T> using MinPQ = priority_queue<T, vector<T>, greater<T>>;
template <class T> using MaxPQ = priority_queue<T>;
int n;
ll k;
vector<ll> a;
vector< vector<int> > g;
bitset<MAXN> used;
vector<int> p;
vector<int> v;
vector<int> h;
ll preCalc(int u, int par) {
//printf("node %d, parent %d, orig %lld\n", u, par, a[u]);
p[u] = par;
for (int& x : g[u]) {
if (x != par) {
a[u] += preCalc(x, u);
//printf("node %d, add var from node %d, updated to %lld\n", u, x, a[u]);
}
}
//printf("node %d, final %lld\n", u, a[u]);
return a[u];
}
void dfs(int u, ll val) {
if (u == -1) return;
a[u] -= val;
dfs(p[u], val);
}
bool comp(int i, int j) {
if (a[i] != a[j]) return a[i] < a[j];
return i < j;
}
void print(vector<ll>& ve) {
for (ll& x : ve) printf("%lld ", x);
printf("\n");
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
scanf("%d %lld", &n, &k);
p.assign(n, -1);
g.assign(n, vector<int>());
a.assign(n, 0);
h.assign(n, 0);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]), h[i] = a[i];
for (int i = 0; i < n - 1; i++) {
int x, y;
scanf("%d %d", &x, &y); --x; --y;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
preCalc(0, -1);
for (int i = 0; i < n; i++) {
v.emplace_back(i);
}
int ans = 0;
while (true) {
sort(v.begin(), v.end(), comp);
bool needSplit = false;
int idx = -1;
for (int i = 0; i < n; i++) {
if (used[v[i]]) {
continue;
}
if (a[v[i]] <= k) {
idx = i;
} else {
needSplit = true;
break;
}
}
if (!needSplit) break;
used[v[idx]] = 1;
/*printf("ops %d:\n", ans);
printf("break the link from %d to %d\n",v[idx], p[v[idx]]);
printf("element to be considered (before):\n");
for (int j = 0; j < n; j ++) {
printf("index %d, val %lld\n", v[j], a[v[j]]);
}*/
ans++;
dfs(p[v[idx]], a[v[idx]]);
/*printf("element to be considered (after):\n");
for (int j = 0; j < n; j ++) {
printf("index %d, val %lld\n", v[j], a[v[j]]);
}*/
//v.erase(v.begin() + idx);
}
printf("%d\n", ans);
return 0;
}
Compilation message
paprike.cpp: In function 'int main()':
paprike.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~~~
paprike.cpp:62:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < n; i++) scanf("%lld", &a[i]), h[i] = a[i];
paprike.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y); --x; --y;
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
428 KB |
Output is correct |
4 |
Correct |
2 ms |
428 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
688 KB |
Output is correct |
9 |
Correct |
2 ms |
688 KB |
Output is correct |
10 |
Correct |
2 ms |
688 KB |
Output is correct |
11 |
Correct |
2 ms |
688 KB |
Output is correct |
12 |
Correct |
2 ms |
732 KB |
Output is correct |
13 |
Correct |
2 ms |
736 KB |
Output is correct |
14 |
Correct |
2 ms |
868 KB |
Output is correct |
15 |
Correct |
2 ms |
868 KB |
Output is correct |
16 |
Incorrect |
2 ms |
868 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
14844 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
428 KB |
Output is correct |
4 |
Correct |
2 ms |
428 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
688 KB |
Output is correct |
9 |
Correct |
2 ms |
688 KB |
Output is correct |
10 |
Correct |
2 ms |
688 KB |
Output is correct |
11 |
Correct |
2 ms |
688 KB |
Output is correct |
12 |
Correct |
2 ms |
732 KB |
Output is correct |
13 |
Correct |
2 ms |
736 KB |
Output is correct |
14 |
Correct |
2 ms |
868 KB |
Output is correct |
15 |
Correct |
2 ms |
868 KB |
Output is correct |
16 |
Incorrect |
2 ms |
868 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
428 KB |
Output is correct |
4 |
Correct |
2 ms |
428 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
2 ms |
596 KB |
Output is correct |
8 |
Correct |
2 ms |
688 KB |
Output is correct |
9 |
Correct |
2 ms |
688 KB |
Output is correct |
10 |
Correct |
2 ms |
688 KB |
Output is correct |
11 |
Correct |
2 ms |
688 KB |
Output is correct |
12 |
Correct |
2 ms |
732 KB |
Output is correct |
13 |
Correct |
2 ms |
736 KB |
Output is correct |
14 |
Correct |
2 ms |
868 KB |
Output is correct |
15 |
Correct |
2 ms |
868 KB |
Output is correct |
16 |
Incorrect |
2 ms |
868 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |