/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Wrong Answer 4ms 572.0 KiB
#2 Wrong Answer 4ms 532.0 KiB
#3 Wrong Answer 4ms 416.0 KiB
#4 Wrong Answer 7ms 824.0 KiB
#5 Time Exceeded ≥1074ms ≥13.473 MiB
#6 Time Exceeded ≥1075ms ≥20.512 MiB
#7 Time Exceeded ≥1080ms ≥12.723 MiB
#8 Wrong Answer 26ms 792.0 KiB
#9 Wrong Answer 389ms 2.031 MiB
#10 Time Exceeded ≥1069ms ≥11.672 MiB
#11 Time Exceeded ≥1077ms ≥16.723 MiB
#12 Time Exceeded ≥1067ms ≥13.105 MiB
#13 Time Exceeded ≥1083ms ≥21.16 MiB
#14 Time Exceeded ≥1071ms ≥14.668 MiB
#15 Wrong Answer 406ms 3.906 MiB
#16 Time Exceeded ≥1075ms ≥28.992 MiB
#17 Time Exceeded ≥1083ms ≥20.742 MiB
#18 Time Exceeded ≥1079ms ≥18.461 MiB
#19 Time Exceeded ≥1088ms ≥14.109 MiB
#20 Time Exceeded ≥1095ms ≥15.059 MiB
#21 Time Exceeded ≥1087ms ≥15.062 MiB
#22 Memory Exceeded ≥1131ms ≥256.016 MiB
#23 Time Exceeded ≥1092ms ≥28.258 MiB
#24 Time Exceeded ≥1094ms ≥28.219 MiB
#25 Time Exceeded ≥1083ms ≥25.805 MiB
#26 Wrong Answer 472ms 193.047 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 root = 0;
vector<int> adj[N];
int depth[N];

void root_find(int node,int par, vector<int> check, vector<int> adj[]){

    for (auto it : adj[node]){
        if(it == par) continue;
        root_find(it, node, check, adj);
        if (!root && check[it]) root = it;
    }
}

int dfs(int node, int cost, int par, vector<int> check, vector<int> adj[]) {

    int tmp = 0;
    for(auto it: adj[node]) {
        if(it == par) continue;

        depth[it] = depth[node] + 1;
        tmp += dfs(it,2,node,check,adj);
    }

    if(tmp == 0 && !check[node]) return 0;

    return tmp + cost;
}

void Hrid_solve(){
    int n;
    cin >> n;

    vector<int> check(n);
    for(int i = 0; i < n; i++) {
        cin >> check[i];
        if(check[i]) root = i;
    } 

    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);
    }

    if(count(all(check),1)==0) {
        cout << 0 << endl;
        return;
    }

    root_find(0,-1,check,adj);
    // cout << root << endl;
    int mx = N;

    int ans = dfs(root,0,-1,check,adj);
    for(int i = 0; i < n; i++) {
        if(check[i]) {
            mx = max(mx, depth[i]);
        }

        adj[i].clear();
        depth[i] = 0;
    }

    cout << ans-mx << endl;
    root = 0;
}


/* ************** 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
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-17 15:19:38
Judged At
2024-10-03 13:17:07
Judged By
Score
0
Total Time
≥1131ms
Peak Memory
≥256.016 MiB