#include "catdog.h"
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
#include <vector>
#include <stdlib.h>
#define INF 100000005
using namespace std;
int x,cats[200005],dogs[200005],tata[200005],niv[200005],nr,valoare[200005];
vector <int> gr[200005];
void dfs(int x,int t,int nivel)
{
tata[x]=t;
niv[x]=nivel;
for (int i=0; i<gr[x].size(); i++)
{
int nod=gr[x][i];
if (nod!=t)
{
dfs(nod,x,nivel+1);
}
}
}
int n2;
void initialize(int n, std::vector<int> A, std::vector<int> B)
{
n2=n;
int i;
for (i=0; i<n-1; i++)
{
gr[A[i]].push_back(B[i]);
gr[B[i]].push_back(A[i]);
}
for (i=1; i<=n; i++)
{
cats[i]=0;
dogs[i]=0;
}
nr=0;
dfs(1,0,1);
}
void solve(int x,int t)
{
for (int i=0;i<gr[x].size();i++)
{
int nod=gr[x][i];
if (nod!=t)
{
solve(nod,x);
}
}
if (valoare[x]==1)
{
dogs[x]=INF;
}
else
if (valoare[x]==2)
{
cats[x]=INF;
}
int i;
for (i=0;i<gr[x].size();i++)
{
int nod=gr[x][i];
if (nod!=t)
{
dogs[x]+=min(dogs[nod],cats[nod]+1);
cats[x]+=min(cats[nod],dogs[nod]+1);
}
}
}
int calculeaza()
{
int i;
for (i=1;i<=n2;i++)
{
cats[i]=dogs[i]=0;
}
solve(1,0);
if (valoare[1]==1)
{
return cats[1];
}
if (valoare[1]==2)
{
return dogs[1];
}
return min(dogs[1],cats[1]);
}
int cat(int v)
{
valoare[v]=1;
return calculeaza();
}
int dog(int v)
{
valoare[v]=2;
return calculeaza();
}
int neighbor(int v)
{
valoare[v]=0;
return calculeaza();
}
/*int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
int N=readInt();
std::vector<int> A(N-1),B(N-1);
for(int i=0;i<N-1;i++)
{
A[i]=readInt();
B[i]=readInt();
}
int Q;
assert(scanf("%d",&Q)==1);
std::vector <int> T(Q),V(Q);
for(int i=0;i<Q;i++)
{
T[i]=readInt();
V[i]=readInt();
}
initialize(N,A,B);
std::vector<int> res(Q);
for(int j=0;j<Q;j++)
{
if(T[j]==1) res[j]=cat(V[j]);
else if(T[j]==2) res[j]=dog(V[j]);
else res[j]=neighbor(V[j]);
}
for(int j=0;j<Q;j++)
printf("%d\n",res[j]);
return 0;
}*/
Compilation message
catdog.cpp: In function 'void dfs(int, int, int)':
catdog.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i=0; i<gr[x].size(); i++)
| ~^~~~~~~~~~~~~
catdog.cpp: In function 'void solve(int, int)':
catdog.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i=0;i<gr[x].size();i++)
| ~^~~~~~~~~~~~~
catdog.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (i=0;i<gr[x].size();i++)
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5000 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
5004 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5008 KB |
Output is correct |
14 |
Correct |
3 ms |
5012 KB |
Output is correct |
15 |
Correct |
3 ms |
5004 KB |
Output is correct |
16 |
Correct |
3 ms |
5004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5000 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
5004 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5008 KB |
Output is correct |
14 |
Correct |
3 ms |
5012 KB |
Output is correct |
15 |
Correct |
3 ms |
5004 KB |
Output is correct |
16 |
Correct |
3 ms |
5004 KB |
Output is correct |
17 |
Correct |
15 ms |
5068 KB |
Output is correct |
18 |
Correct |
20 ms |
5104 KB |
Output is correct |
19 |
Correct |
11 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5004 KB |
Output is correct |
21 |
Correct |
5 ms |
4940 KB |
Output is correct |
22 |
Correct |
6 ms |
4940 KB |
Output is correct |
23 |
Correct |
21 ms |
5012 KB |
Output is correct |
24 |
Correct |
17 ms |
5092 KB |
Output is correct |
25 |
Correct |
9 ms |
5060 KB |
Output is correct |
26 |
Correct |
6 ms |
5060 KB |
Output is correct |
27 |
Correct |
6 ms |
5136 KB |
Output is correct |
28 |
Correct |
6 ms |
5068 KB |
Output is correct |
29 |
Correct |
20 ms |
5144 KB |
Output is correct |
30 |
Correct |
5 ms |
4940 KB |
Output is correct |
31 |
Correct |
4 ms |
5068 KB |
Output is correct |
32 |
Correct |
6 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5000 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
5004 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5008 KB |
Output is correct |
14 |
Correct |
3 ms |
5012 KB |
Output is correct |
15 |
Correct |
3 ms |
5004 KB |
Output is correct |
16 |
Correct |
3 ms |
5004 KB |
Output is correct |
17 |
Correct |
15 ms |
5068 KB |
Output is correct |
18 |
Correct |
20 ms |
5104 KB |
Output is correct |
19 |
Correct |
11 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5004 KB |
Output is correct |
21 |
Correct |
5 ms |
4940 KB |
Output is correct |
22 |
Correct |
6 ms |
4940 KB |
Output is correct |
23 |
Correct |
21 ms |
5012 KB |
Output is correct |
24 |
Correct |
17 ms |
5092 KB |
Output is correct |
25 |
Correct |
9 ms |
5060 KB |
Output is correct |
26 |
Correct |
6 ms |
5060 KB |
Output is correct |
27 |
Correct |
6 ms |
5136 KB |
Output is correct |
28 |
Correct |
6 ms |
5068 KB |
Output is correct |
29 |
Correct |
20 ms |
5144 KB |
Output is correct |
30 |
Correct |
5 ms |
4940 KB |
Output is correct |
31 |
Correct |
4 ms |
5068 KB |
Output is correct |
32 |
Correct |
6 ms |
5068 KB |
Output is correct |
33 |
Execution timed out |
3055 ms |
10084 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |