/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 580.0 KiB
#2 Accepted 4ms 576.0 KiB
#3 Wrong Answer 4ms 588.0 KiB
#4 Wrong Answer 5ms 572.0 KiB
#5 Wrong Answer 27ms 2.25 MiB
#6 Wrong Answer 47ms 2.25 MiB
#7 Wrong Answer 37ms 2.418 MiB
#8 Wrong Answer 18ms 592.0 KiB
#9 Wrong Answer 42ms 848.0 KiB
#10 Wrong Answer 59ms 2.316 MiB
#11 Wrong Answer 40ms 2.492 MiB
#12 Wrong Answer 43ms 2.312 MiB
#13 Wrong Answer 21ms 2.332 MiB
#14 Wrong Answer 61ms 2.496 MiB
#15 Wrong Answer 25ms 880.0 KiB
#16 Wrong Answer 18ms 2.25 MiB
#17 Wrong Answer 18ms 2.242 MiB
#18 Wrong Answer 21ms 2.387 MiB
#19 Accepted 68ms 13.301 MiB
#20 Wrong Answer 67ms 13.113 MiB
#21 Wrong Answer 65ms 13.172 MiB
#22 Accepted 85ms 21.75 MiB
#23 Wrong Answer 139ms 12.59 MiB
#24 Wrong Answer 132ms 12.797 MiB
#25 Wrong Answer 82ms 12.582 MiB
#26 Wrong Answer 8ms 1.305 MiB

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-10-03 13:18:27
Judged By
Score
16
Total Time
139ms
Peak Memory
21.75 MiB