/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 532.0 KiB
#3 Wrong Answer 1ms 512.0 KiB
#4 Wrong Answer 4ms 576.0 KiB
#5 Time Exceeded ≥1088ms ≥13.789 MiB
#6 Time Exceeded ≥1091ms ≥22.84 MiB
#7 Time Exceeded ≥1074ms ≥13.199 MiB
#8 Wrong Answer 28ms 784.0 KiB
#9 Wrong Answer 129ms 2.098 MiB
#10 Time Exceeded ≥1089ms ≥15.812 MiB
#11 Time Exceeded ≥1072ms ≥17.047 MiB
#12 Time Exceeded ≥1081ms ≥18.852 MiB
#13 Time Exceeded ≥1085ms ≥21.676 MiB
#14 Time Exceeded ≥1077ms ≥14.977 MiB
#15 Wrong Answer 127ms 3.418 MiB
#16 Wrong Answer 927ms 29.301 MiB
#17 Time Exceeded ≥1077ms ≥21.406 MiB
#18 Wrong Answer 981ms 19.801 MiB
#19 Time Exceeded ≥1095ms ≥16.727 MiB
#20 Time Exceeded ≥1077ms ≥17.5 MiB
#21 Time Exceeded ≥1096ms ≥17.641 MiB
#22 Memory Exceeded ≥1130ms ≥256.016 MiB
#23 Time Exceeded ≥1087ms ≥30.648 MiB
#24 Time Exceeded ≥1085ms ≥30.664 MiB
#25 Time Exceeded ≥1094ms ≥28.289 MiB
#26 Wrong Answer 191ms 193.0 MiB

Code

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define all(v) (v).begin(), (v).end()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define F first 
#define S second

const ll M = 1e18 + 7;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;

int cnt = 0;
vector<int> tmp;

int dfs(int node, int ans, vector<int> &lvl,
    vector<int> &vis, vector<int> check, vector<int> adj[]) {
    
    vis[node] = 1;
    if(check[node]) tmp.push_back(node);

    int cost = 0;
    for(auto it: adj[node]) {
        if(!vis[it]) {
            // lvl[it] = lvl[node]+1;

            cost += dfs(it,2,lvl,vis,check,adj);
            // lvl[node] = max(lvl[node],lvl[it]+1);
        }
    } 

    if(cost==0) {
        if(check[node] == 0) {
            return 0;
        }
    }

    return ans+cost;
}

void dfs2(int node, int n ,vector<int> &lvl,
    vector<int> adj[])
{  
    queue<int> q;
    q.push(node);
    int vis[n] = {0};

    while(!q.empty()) {
        int v = q.front();
        q.pop();

        for(auto it: adj[v]){
            if(!vis[it]) {
                vis[it] = 1;
                lvl[it] = lvl[v]+1;
                q.push(it);
            }
        }
    }
}


void Hrid_solve(){
    int n;
    cin >> n;
    vector<int> check(n), vis(n,0),lvl(n,0);
    for(auto &i: check) cin >> i;

    vector<int> adj[n];
    for(int i = 0; i < n-1; i++) {
        int u,v;
        cin >> u >> v;
        u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(check[i]) {
            dfs2(i,n,lvl,adj);
            ans = dfs(0,0,lvl,vis,check,adj);
            break;
        }
    }
    // for(int i = 0; i < n; i++) {
    //     cout <<i+1 << " " << lvl[i] << endl;
    // }

    // for(auto i: tmp) cout << i << " ";
    // cout << endl;
    // cout << tmp[0] << " " << lvl[tmp[0]] << endl;
    cout << ans-lvl[tmp[0]] << endl;

    tmp.clear();
    
}


/* ************** What defines us is how well we rise after we Fall !! ************** */

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
 
    int tc = 1;
    cin >> tc;
    for(int kase = 1; kase <= tc; kase++){
        // cout << "Case " << kase << ": ";
        Hrid_solve();
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 17:42:01
Judged At
2024-10-03 13:21:09
Judged By
Score
1
Total Time
≥1130ms
Peak Memory
≥256.016 MiB