QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#857278 | #9987. 骑行计划 | myloveATRI | RE | 0ms | 0kb | C++20 | 2.0kb | 2025-01-15 14:57:31 | 2025-01-15 14:57:32 |
Judging History
answer
#include<bits/stdc++.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define int long long
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define nl t[n].l
#define nr t[n].r
#define gcd __gcd
#define itn int
#define db long double
using namespace std;
const int maxn=1e6+50;
const int inf=1e18+10;
const int INF=2e18;
const int mod=998244353;
//const db eps=1e-8;
//const db pi=acos(-1.0);
#define pop_count __builtin_popcountll
vector<int> g[maxn];
int f[maxn][5];
int is[maxn];
//0白 1灰下白 2 灰下黑 3黑 4灰下灰
void dfs(itn n,int fa)
{
f[n][0]=1;
f[n][1]=f[n][2]=0;
if(is[n])
{
f[n][3]=0;
f[n][0]=inf;
f[n][1]=f[n][2]=f[n][4]=inf;
}
else f[n][3]=inf;
int ok=0;
for(auto x:g[n])
{
if(x==fa) continue;
dfs(x,n);
ok|=is[x];
if(is[n])
{
f[n][3]+=min({f[x][0],f[x][1],f[x][3]});
}
}
if(is[n]) return;
if(1)
{
int tot=inf;
for(auto x:g[n])
{
if(x==fa) continue;
f[n][0]+=min({f[x][0],f[x][1],f[x][2],f[x][3],f[x][4]});
f[n][2]+=min({f[x][1],f[x][3],f[x][4]});
tot=min(tot,f[x][0]-min({f[x][0],f[x][1],f[x][2],f[x][3],f[x][4]}));
if(ok) f[n][4]=inf;
else{
f[n][4]+=min(f[n][1],f[n][4]);
}
}
f[n][1]=f[n][0]-1+tot;
}
}
void solve(){
int n,k;
cin>>n>>k;
rep(i,1,k)
{
int u;
cin>>u;
is[u]=1;
}
rep(i,1,n-1)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<min({f[1][0],f[1][1],f[1][2],f[1][3],f[1][4]});
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int __=1;
srand((time(0)));
// cin>>__;
while(__--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
85 5408 4856 52 43 38 21 33 28 24 46 4 66 14 51 63 24 69 35 50 9 63 58 43 69 1 28 59 56 50 63 12 23 41 6 19 9 41 45 14 52 6 7 1 24 30 9 33 54 71 38 55 28 61 10 21 13 22 56 29 24 19 27 9 3 25 54 45 50 9 42 13 5 32 37 56 51 24 3 12 37 68 29 69 40 53 50 69 486593 41 10 175445 13 5 1271250 9 35 7064 1 2...