QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#857278#9987. 骑行计划myloveATRIRE 0ms0kbC++202.0kb2025-01-15 14:57:312025-01-15 14:57:32

Judging History

This is the latest submission verdict.

  • [2025-01-15 14:57:32]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2025-01-15 14:57:31]
  • 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黑 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...

output:


result: