ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#208409 | #3792. Water and Ice | mygr | 100 | 311ms | 11836kb | C++ | 2.5kb | 2024-08-02 12:39:27 | 2024-08-02 12:58:14 |
answer
#include<bits/stdc++.h>
using namespace std;
const int Max=4e5+5;
class so1{
public:
struct edge{
int to,next;
}p[Max*2];
int head[Max],last[Max],idx;
void add(int u,int v)
{
if(!head[u])
head[u]=++idx;
else
p[last[u]].next=++idx;
last[u]=idx;
p[idx].to=v;
}
int n,d;
int ans[Max],cnt,fin,fans[Max];
bool check(int now,int from,int dep)
{
if(from!=now and ans[now])
return 1;
if(dep==d-1)
return 0;
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
if(check(p[i].to,now,dep+1))
return 1;
}
return 0;
}
void dfs(int dep)
{
if(dep>n)
{
if(cnt<=fin)
return ;
for(int i=1;i<=n;i++)
if(ans[i] and check(i,i,0))
return ;
fin=max(fin,cnt);
for(int i=1;i<=n;i++)
fans[i]=ans[i];
return ;
}
ans[dep]=1;
cnt++;
dfs(dep+1);
ans[dep]=0;
cnt--;
dfs(dep+1);
}
void solve()
{
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1);
printf("%d\n",fin);
for(int i=1;i<=n;i++)
if(fans[i])
printf("%d ",i);
}
}s1;
class so2{
public:
struct edge{
int to,next;
}p[Max*2];
int head[Max],last[Max],idx=0;
void add(int u,int v)
{
if(!head[u])
head[u]=++idx;
else
p[last[u]].next=++idx;
last[u]=idx;
p[idx].to=v;
}
int dep[Max],fa[Max],f[Max];
int vis[Max];
void dfs(int now,int from)
{
dep[now]=dep[from]+1;
fa[now]=from;
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
dfs(p[i].to,now);
}
}
int n,d;
void paint(int now,int dep)
{
for(int i=1;i<=d;i++,now=fa[now])
f[now]=max(f[now],d-i+1);
}
bool check(int now)
{
int nt=now;
for(int i=1;i<=d;i++,nt=fa[nt])
if(f[nt]>=i)
{
for(int j=1;now!=nt;j++,now=fa[now])
f[now]=max(f[now],f[nt]-(dep[now]-dep[nt]));
return 0;
}
return 1;
}
pair<int,int> e[Max];
int ans[Max],cnt=0;
void solve()
{
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,1);
for(int i=1;i<=n;i++)
e[i]=make_pair(dep[i],i);
sort(e+1,e+1+n);
for(int i=n;i>=1;i--)
{
if(check(e[i].second))
{
ans[++cnt]=e[i].second;
paint(e[i].second,d);
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%d ",ans[i]);
}
}s2;
int n,d;
int main()
{
scanf("%d%d",&n,&d);
if(n<=20)
{
s1.n=n;s1.d=d;
s1.solve();
}
else
{
s2.n=n;s2.d=d;
s2.solve();
}
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 4352kb
input:
10 5 3 7 7 10 7 8 9 1 5 4 3 9 7 5 3 2 7 6
output:
2 1 4
result:
ok ok accepted
Test #2:
score: 10
Accepted
time: 0ms
memory: 4352kb
input:
10 4 8 5 8 6 1 8 4 9 5 3 7 10 8 4 7 2 1 7
output:
3 2 3 9
result:
ok ok accepted
Test #3:
score: 10
Accepted
time: 0ms
memory: 4352kb
input:
10 3 7 8 1 10 4 3 1 5 1 7 2 9 1 4 7 2 2 6
output:
4 3 5 6 8
result:
ok ok accepted
Test #4:
score: 10
Accepted
time: 0ms
memory: 4464kb
input:
3000 4 609 550 550 37 550 460 460 2476 2476 822 460 18 822 740 609 1212 822 2274 740 2276 2276 187 4...
output:
778 2803 2146 6 205 2371 2109 1212 869 1284 18 1031 1226 883 2694 1020 1651 45 573 38 2376 2333 747 ...
result:
ok ok accepted
Test #5:
score: 10
Accepted
time: 3ms
memory: 4456kb
input:
3000 10 29 699 699 832 29 2332 29 1385 699 1783 832 734 1385 1639 734 2853 29 2689 2853 2190 699 558...
output:
220 1728 539 1696 884 271 62 1893 1561 433 2000 2795 2906 1708 2637 152 2698 1630 1504 2904 2437 167...
result:
ok ok accepted
Test #6:
score: 10
Accepted
time: 0ms
memory: 4456kb
input:
3000 50 444 813 444 135 813 2265 135 2309 135 914 914 535 135 2055 2055 1225 914 2499 2055 1364 2499...
output:
20 2137 824 2544 1275 1427 2538 2634 20 2893 90 2199 2553 2395 2556 2973 789 2900 2793 667 208
result:
ok ok accepted
Test #7:
score: 10
Accepted
time: 88ms
memory: 11836kb
input:
200000 217 31004 146202 108924 82624 43788 48134 199877 157947 92879 87010 198989 49945 175154 66735...
output:
924 67456 35624 127539 92910 73540 25439 184428 85006 130464 13791 155457 172171 61710 164999 80784 ...
result:
ok ok accepted
Test #8:
score: 10
Accepted
time: 92ms
memory: 11452kb
input:
200000 475 77454 87171 23492 138432 137402 34171 181862 18661 57910 51505 135417 198061 164845 19388...
output:
394 60394 57846 64389 50025 12771 33384 115452 176700 7839 915 182340 110299 128738 10851 62139 1713...
result:
ok ok accepted
Test #9:
score: 10
Accepted
time: 48ms
memory: 11768kb
input:
199999 4 1 2 2 3 1 4 4 5 1 6 6 7 1 8 8 9 1 10 10 11 1 12 12 13 1 14 14 15 1 16 16 17 1 18 18 19 1 20...
output:
99999 199999 199997 199995 199993 199991 199989 199987 199985 199983 199981 199979 199977 199975 199...
result:
ok ok accepted
Test #10:
score: 10
Accepted
time: 80ms
memory: 11376kb
input:
199397 946 29518 79973 29518 71183 71183 194147 29518 156561 156561 196558 196558 25260 29518 198870...
output:
159 156440 134941 66823 173468 85215 105244 123376 168267 169990 112932 174647 117477 163036 32323 3...
result:
ok ok accepted