QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#857267#9996. 辞甲猾扎myloveATRIWA 516ms109132kbC++201.9kb2025-01-15 14:40:042025-01-15 14:40:06

Judging History

This is the latest submission verdict.

  • [2025-01-15 14:40:06]
  • Judged
  • Verdict: WA
  • Time: 516ms
  • Memory: 109132kb
  • [2025-01-15 14:40:04]
  • Submitted

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黑
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]=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[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[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]});
}


signed main()
{
   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int __=1;
   srand((time(0)));
  // cin>>__;
  while(__--)
  {
       solve();
  }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 516ms
memory: 109132kb

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:

278332

result:

wrong answer 1st lines differ - expected: '497', found: '278332'