QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#857298 | #9996. 辞甲猾扎 | myloveATRI | WA | 595ms | 110420kb | C++20 | 2.1kb | 2025-01-15 15:17:14 | 2025-01-15 15:17:15 |
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]});
if(ok)
f[n][2]+=min({f[x][1],f[x][3],f[x][4]});
else f[n][2]=inf;
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[x][1],f[x][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<<f[1][4];
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: 100
Accepted
time: 589ms
memory: 109496kb
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:
497
result:
ok single line: '497'
Test #2:
score: -100
Wrong Answer
time: 595ms
memory: 110420kb
input:
1000000 200000 9 11 14 17 27 43 45 51 54 56 65 68 69 79 80 81 83 100 104 111 112 113 118 119 121 122 126 140 141 142 144 148 152 156 159 160 161 175 180 181 187 188 189 194 196 208 219 237 242 243 245 247 250 254 255 272 286 291 297 302 307 310 312 316 317 324 325 326 327 330 334 340 350 357 358 361...
output:
208982
result:
wrong answer 1st lines differ - expected: '216049', found: '208982'