/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 576.0 KiB
#2 Accepted 4ms 588.0 KiB
#3 Wrong Answer 4ms 532.0 KiB
#4 Wrong Answer 5ms 644.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define nl '\n'
const int N = 200000+9;
vector<int> graph[N] ;
bool vis[N] , marked[N] , vis1[N];
int aa[N] , ans , counter;
bool dsf(int i){
    vis[i] =1 ;
    bool flag = 0 ;
    for(auto it : graph[i]){
        if(!vis[it]){
            if(dsf(it) == 1){
                flag = 1 ;
            }
        }
    }
    if(aa[i] == 1 or flag == 1){
        marked[i] = 1 ;
        return 1 ;
    }
    else{
        return 0 ;
    }
    
}
void dfs2(int i){
    vis1[i] = 1 ;
    counter++;
    bool flag = 0 ;
    for(auto it : graph[i]){
        if((vis1[it] == 0) and (marked[it] == 1)){
            flag = 1 ;
            //cout<< it << " " << vis1[it] << " " << marked[it] << nl;
            dfs2(it);
        }
    }
    if(flag == 0){
        ans = counter ;
    }
    counter++;
}

void solve()
{
    
    int n ;cin>> n ;
    for(int i=1 ; i<=n ; i++){
        graph[i].clear();
        vis[i] = 0 ;
        vis1[i] = 0 ;
        marked[i] = 0 ;
    }
    ans = 0 , counter = 0 ;
    int first = -69 ;
    for(int i=1 ; i<=n ; i++){
        cin>> aa[i];
    }
    for(int i=1 ; i<=n ; i++){
        if(aa[i] == 1){
            first = i ;
            break;
        }
    }
    for(int i=1 ; i<=n-1 ; i++){
        int u , v ; cin>> u >> v ;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    if(first == -69){
        cout<< 0 << nl;
        return;
    }
    //cout<< first << nl;
    if(dsf(first)){
        marked[first]= 1 ;
    }
    
    for(int i=1 ; i<=n ; i++){
        //cout<< marked[i] << " ";
        if(aa[i] == 1){
            first = i ;
            break;
        }
    }
    /*for(int i=1 ; i<=n ; i++){
        cout<< vis1[i] << " ";
    }
    cout<< nl;
    for(int i=1 ; i<=n ; i++){
        cout<< marked[i] << " ";
    }
    cout<< nl;*/
    
    dfs2(first);
    cout<< ans-1 << nl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int T ;
    cin >> T ;
    for (int tt = 1 ; tt <= T ; tt++)
    {
        solve() ;
    }
}

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-17 09:21:15
Judged At
2024-11-11 03:09:01
Judged By
Score
4
Total Time
5ms
Peak Memory
644.0 KiB