QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297711 | #7936. Eliminate Tree | Rifal | WA | 108ms | 44008kb | C++17 | 3.6kb | 2024-01-05 03:02:51 | 2024-01-05 03:02:52 |
Judging History
answer
#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 10000000000
#define INF 1000000000
#define INF2 2000000000000000000
//#define ll long long
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
const int M = 2e5 + 5;
vector<int> v[M];
set<int> st[M];
int par[M];
bool ok[M], ok2[M];
void dfs(int s, int p) {
par[s] = p;
for(auto i : v[s]) {
if(i != p) {
dfs(i,s); }
}
}
int main()
{
ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
int n; cin >> n;
for(int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
st[a].insert(b);
st[b].insert(a);
}
if(n == 1) {
cout << 2 << endl; return 0;
}
else if(n == 2) {
cout << 1 << endl; return 0;
}
dfs(1,0); deque<int> dq;
for(int i = 1; i <= n; i++) {
if(v[i].size() == 1) {
ok[i] = 1;
if(i == 1) {
if(v[v[1][0]].size() <= 2) {
dq.push_front(i);
}
else {
dq.push_back(i);
}
}
else {
if(v[par[i]].size() <= 2) {
dq.push_front(i);
}
else {
dq.push_back(i);
}
}
}
}
int ans = 0;
while(!dq.empty()) {
int x = dq.front(); dq.pop_front();
int y = -1;
if(ok2[x] == 1) continue;
ok2[x] = 1;
if(st[x].size() == 0) {
ans += 2; continue; }
if(st[par[x]].size() <= 0) {
int child = *st[x].begin();
if(st[child].size() <= 2 && st[child].size() > 0) {
ans++;
}
else {
ans += 2;
}
for(auto i : st[x]) {
st[i].erase(x);
}
st[x].clear();
if(st[child].size() == 1) {
y = *st[child].begin();
}
if(st[child].size() <= 1) {
for(auto i : st[child]) {
st[i].erase(child);
}
st[child].clear();
ok[child] = 1;
ok2[child]=1;
}
}
else {
if(st[par[x]].size() <= 2 && st[par[x]].size() > 0) {
ans++;
}
else {
ans += 2;
}
for(auto i : st[x]) {
st[i].erase(x);
}
st[x].clear();
if(st[par[x]].size() == 1) {
y = *st[par[x]].begin();
}
if(st[par[x]].size() <= 1) {
for(auto i : st[par[x]]) {
st[i].erase(par[x]);
}
st[par[x]].clear();
ok[par[x]] = 1;
ok2[par[x]] = 1;
}
}
// cout << x << ' ' << y << endl;
if(y != -1 && st[y].size() <= 1 && ok[y] == 0 && ok2[y] == 0) { ok[y] = 1; dq.push_front(y); }
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18504kb
input:
5 1 2 2 3 3 4 3 5
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 3ms
memory: 17596kb
input:
4 1 2 2 3 3 4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 108ms
memory: 44008kb
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:
162470
result:
wrong answer 1st numbers differ - expected: '138182', found: '162470'