This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "catdog.h"
#include<bits/stdc++.h>
int n;
std::vector<int> adj[100001];
int oc[100001];
int rbct = 0;
int ctct = 0;
int dgct = 0;
int actct[100001];
int adgct[100001];
int bctct[100001];
int bdgct[100001];
bool visited[100001];
void dfs (int node)
{
if (visited[node]) return;
visited[node] = true;
actct[node] = ctct;
adgct[node] = dgct;
//std:cout << node << "\n";
for (unsigned int u = 0; u < adj[node].size(); ++u)
{
if (visited[adj[node][u]]) continue;
dfs(adj[node][u]);
if (oc[node] == 1 && dgct != 0) {dgct = 0; ++rbct;}
else if (oc[node] == 2 && ctct != 0) {ctct = 0; ++rbct;}
else
{
if (ctct - actct[node] != 0) {++bctct[node]; actct[node] = ctct;}
if (dgct - adgct[node] != 0) {++bdgct[node]; adgct[node] = dgct;}
}
}
if (bctct[node] < bdgct[node] && bctct[node] != 0) {ctct = 0; rbct += bctct[node];}
else if (bdgct[node] <= bctct[node] && bdgct[node] != 0) {dgct = 0; rbct += bdgct[node];}
if (oc[node] == 1) ++ctct;
else if (oc[node] == 2) ++dgct;
}
void initialize(int N, std::vector<int> A, std::vector<int> B)
{
n = N;
for (int i = 0; i < n-1; ++i)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
std::memset(oc, 0, sizeof oc);
}
int cat(int v)
{
oc[v] = 1;
rbct = 0;
ctct = 0;
dgct = 0;
std::memset(visited, false, sizeof visited);
std::memset(actct, 0, sizeof actct);
std::memset(adgct, 0, sizeof adgct);
std::memset(bctct, 0, sizeof bctct);
std::memset(bdgct, 0, sizeof bdgct);
dfs(1);
return rbct;
}
int dog(int v)
{
oc[v] = 2;
rbct = 0;
ctct = 0;
dgct = 0;
std::memset(visited, false, sizeof visited);
std::memset(actct, 0, sizeof actct);
std::memset(adgct, 0, sizeof adgct);
std::memset(bctct, 0, sizeof bctct);
std::memset(bdgct, 0, sizeof bdgct);
dfs(1);
return rbct;
}
int neighbor(int v)
{
oc[v] = 0;
rbct = 0;
ctct = 0;
dgct = 0;
std::memset(visited, false, sizeof visited);
std::memset(actct, 0, sizeof actct);
std::memset(adgct, 0, sizeof adgct);
std::memset(bctct, 0, sizeof bctct);
std::memset(bdgct, 0, sizeof bdgct);
dfs(1);
return rbct;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |