QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#365340 | #7936. Eliminate Tree | Infused | WA | 109ms | 33508kb | C++20 | 1.7kb | 2024-03-25 04:00:43 | 2024-03-25 04:00:44 |
Judging History
answer
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define db puts("*****")
#define sz(x) int(x.size())
#define pii pair <int , int>
#define mid(x , y) ((x+y)>>1)
#define all(x) x.begin(),x.end()
#define y1 your_name_engraved_herein
using namespace std;
const int N = 2e5+2;
const int K = 1e3+2;
const int MOD = 998244353;
template<class T> bool umin(T& a, T b) { if(a > b){ a = b; return 1; } return 0; }
template<class T> bool umax(T& a, T b) { if(a < b){ a = b; return 1; } return 0; }
int lvl[N], par[N], cnt;
set<int> E[N];
void dfs(int u, int p){
par[u] = p;
lvl[u] = lvl[p] + 1;
for(int v : E[u]){
if(v != p){
dfs(v, u);
}
}
}
void solve(){
int n; scanf("%d", &n);
for(int i=0; i<n-1; i++){
int a, b; scanf("%d%d", &a, &b);
E[a].insert(b);
E[b].insert(a);
}
dfs(1, 0);
vector<int> v(n);
for(int i=0; i<n; i++){
v[i] = i+1;
}
sort(all(v), [&](int x, int y){
return lvl[x] > lvl[y];
});
vector<bool> out(n+1, false);
int ans = 0;
for(int u : v){
if(out[u]) continue;
if(u == 1){
ans += 2;
out[u] = true;
} else if(sz(E[par[u]]) <= 2) {
ans += 1;
out[u] = out[par[u]] = true;
if(par[u] != 1){
E[par[par[u]]].erase(par[u]);
}
} else {
out[u] = true;
ans += 2;
E[par[u]].erase(u);
}
}
printf("%d\n", ans);
}
int main(){
int testcase = 1;
// scanf("%d", &testcase);
while(testcase--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14648kb
input:
5 1 2 2 3 3 4 3 5
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 13456kb
input:
4 1 2 2 3 3 4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 109ms
memory: 33508kb
input:
196666 32025 108673 181779 17115 162570 134230 93003 39673 89144 1269 185919 154408 34896 65369 35860 44720 55698 1390 45520 189805 147867 124511 135459 132555 87303 18031 176314 59695 33352 130640 87272 39716 35749 108807 143493 94486 126512 116598 40212 70895 132216 80855 22241 188737 150354 17346...
output:
138182
result:
ok 1 number(s): "138182"
Test #4:
score: -100
Wrong Answer
time: 95ms
memory: 32880kb
input:
192941 180913 51977 128686 137679 118562 93198 60438 181978 39944 140001 169718 122100 146644 138935 22544 124591 113645 112480 128660 133392 9985 102696 4089 62155 4760 3202 116481 17579 59343 141071 81968 156270 5544 186622 117322 35780 127098 110151 148427 70933 2244 44243 3778 176132 181512 1583...
output:
135477
result:
wrong answer 1st numbers differ - expected: '135478', found: '135477'