Submission #2123639
Source Code Expand
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define CL fclose(stdin),fclose(stdout)
namespace io
{
int F()
{
int n=0,F=1;
char ch;
while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
ch=='-'?F=0:n=ch-'0';
while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
return F?n:-n;
}
long long G()
{
long long n=0,F=1;
char ch;
while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
ch=='-'?F=0:n=ch-'0';
while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
return F?n:-n;
}
}
struct edge
{
int to;
int next;
}e[333333];
int pe=111111;
int deg[111111];
void insert(int a,int to)
{
e[pe]=(edge){to,e[a].next};
e[a].next=pe++;
deg[to]++;
}
int f[111111][4];//1:ex 2:ex0
void dfs(int o,int fa)
{
if(deg[o]==1){f[o][2]=0,f[o][1]=1;return;}
int g[4]={0,0x3f3f3f3f};
int cnt=0,son;
for(register int p=e[o].next;p;p=e[p].next)
if(e[p].to!=fa)++cnt,son=e[p].to;
if(cnt==1){dfs(son,o);memcpy(f[o],f[son],sizeof(f[o]));return;}
if(cnt==2)
{
int c1=son,c2;
for(register int p=e[o].next;p;p=e[p].next)
if(e[p].to!=fa){c2=e[p].to;break;}
dfs(c1,o);
dfs(c2,o);
int m1=0x3f3f3f3f,m2=0x3f3f3f3f;
cmin(m1,f[c1][0]),cmin(m1,f[c1][1]),cmin(m1,f[c1][3]);
cmin(m2,f[c2][0]),cmin(m2,f[c2][1]),cmin(m2,f[c2][3]);
f[o][1]=m1+m2;
cmin(f[o][3],f[c1][1]+f[c2][2]);
cmin(f[o][3],f[c1][2]+f[c2][1]);
cmin(f[o][0],f[c1][0]+f[c2][2]);
cmin(f[o][0],f[c1][2]+f[c2][0]);
cmin(f[o][0],f[c1][2]+f[c2][3]);
cmin(f[o][0],f[c1][3]+f[c2][2]);
return;
}
for(register int p=e[o].next;p;p=e[p].next)
if(e[p].to!=fa)
{
dfs(e[p].to,o);
int mn=0x3f3f3f3f;
for(register int i=0;i<=3;++i)if(i!=2)cmin(mn,f[e[p].to][i]);
g[1]+=mn;
cmin(g[1],g[0]+f[e[p].to][2]);
g[0]+=mn;
}
f[o][3]=g[1];
f[o][1]=g[0];
}
int main()
{
int n=io::F();
if(n==2){puts("1");return 0;}
for(register int i=1;i<n;++i)
{
int x=io::F(),y=io::F();
insert(x,y);
insert(y,x);
}
memset(f,63,sizeof(f));
for(register int i=0;i<n;++i)
if(deg[i]!=1){dfs(i,i);printf("%d\n",dmin(f[i][1],f[i][3]));break;}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Antennas on Tree |
User |
ESpace |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
2349 Byte |
Status |
AC |
Exec Time |
20 ms |
Memory |
12544 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
3968 KB |
0_01.txt |
AC |
1 ms |
128 KB |
0_02.txt |
AC |
2 ms |
3968 KB |
1_00.txt |
AC |
1 ms |
128 KB |
1_01.txt |
AC |
2 ms |
3968 KB |
1_02.txt |
AC |
2 ms |
3968 KB |
1_03.txt |
AC |
2 ms |
3968 KB |
1_04.txt |
AC |
2 ms |
3968 KB |
1_05.txt |
AC |
2 ms |
3968 KB |
1_06.txt |
AC |
20 ms |
12544 KB |
1_07.txt |
AC |
13 ms |
4736 KB |
1_08.txt |
AC |
19 ms |
9472 KB |
1_09.txt |
AC |
13 ms |
4736 KB |
1_10.txt |
AC |
19 ms |
9472 KB |
1_11.txt |
AC |
18 ms |
6784 KB |
1_12.txt |
AC |
16 ms |
5120 KB |
1_13.txt |
AC |
17 ms |
4864 KB |
1_14.txt |
AC |
17 ms |
4736 KB |
1_15.txt |
AC |
16 ms |
4736 KB |
1_16.txt |
AC |
16 ms |
4736 KB |
1_17.txt |
AC |
16 ms |
4736 KB |
1_18.txt |
AC |
15 ms |
4736 KB |
1_19.txt |
AC |
15 ms |
4736 KB |
1_20.txt |
AC |
14 ms |
4736 KB |
1_21.txt |
AC |
14 ms |
4736 KB |
1_22.txt |
AC |
13 ms |
4736 KB |