이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
typedef pair <int, int> pii;
const int MAXN = 3e6 + 5;
int n, k;
int ljutina[MAXN];
vector <vector <int> > veze;
bool finito[MAXN];
set <pii> paprika;
set <int> npaprika;
int rezovi, ostalo;
void ispis_ljutina() {
cout << "ljutina\n";
for (int i = 0; i < n; i++) {
cout << ljutina[i] << " ";
}
cout << '\n';
}
void ispis_veze() {
cout << "veze\n";
for (int i = 0; i < n; i++) {
cout << i << " : ";
for (auto x : veze[i]) cout << x << " ";
cout << '\n';
}
}
void ispis_paprika() {
cout << "paprika\n";
for (auto x : paprika) {
cout << x.X << " " << x.Y << '\n';
}
}
void odradi(int x) {
ostalo--;
int z = veze[x][0];
//cout << x << " - " << z << '\n';
if (ljutina[x] + ljutina[z] <= k) {
ljutina[z] += ljutina[x];
}
else rezovi++;
veze[z].erase(remove(veze[z].begin(), veze[z].end(), x), veze[z].end());
veze[x].clear();
if (veze[z].empty()) {
ostalo--;
return;
}
npaprika.insert(z);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> ljutina[i];
int a, b;
veze.resize(n + 5);
for (int i = 1; i < n; i++) {
cin >> a >> b;
--a; --b;
veze[a].pb(b);
veze[b].pb(a);
}
for (int i = 0; i < n; i++) {
if (veze[i].size() == 1) paprika.insert({ljutina[i], i});
}
ostalo = n;
while (ostalo > 0) {
//cout << "ostalo\n" << ostalo << '\n';
//ispis_paprika();
//ispis_veze();
//cout << "povezivanja\n";
npaprika.clear();
for (auto x : paprika) {
odradi(x.Y);
}
paprika.clear();
for (auto x : npaprika) {
paprika.insert({ljutina[x], x});
}
}
cout << rezovi << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |