QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#857273 | #9996. 辞甲猾扎 | myloveATRI | WA | 538ms | 108900kb | C++20 | 2.0kb | 2025-01-15 14:49:35 | 2025-01-15 14:49:36 |
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]);
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
Wrong Answer
time: 538ms
memory: 108900kb
input:
1000000 250 4246 6001 15765 16292 18291 18607 20931 24218 25916 28742 34837 37283 38797 38805 45707 47625 47981 55382 60377 60815 61528 71455 73316 79270 81165 88222 93488 95638 99798 100415 100686 107252 107624 110367 116459 118365 121070 130962 131316 132856 141146 152992 153050 154652 156855 1669...
output:
0
result:
wrong answer 1st lines differ - expected: '497', found: '0'