Submission #1370863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370863		edga1	Tree (IOI24_tree)	C++20	7 / 100	46 ms	22044 KiB

tree

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#include "tree.h"
using namespace std;

const int N=200005;
vector<int> g[N];
int w[N];
ll n,l,r,leaf=0;

void dfs(int v, int p){
    if(g[v].size()==1 && v!=0){
        leaf++;
        return;
    }
    for(auto u : g[v]){
        if(u==p) continue;
        dfs(u,v);
    }
    return;
}

void init(vector<int> P, vector<int> W) {
    n=(int)P.size();
    for(int i=0; i<n; i++) w[i]=W[i];
    for(int i=1; i<n; i++){
        g[i].pb(P[i]);
        g[P[i]].pb(i);
    }
    dfs(0,0);
}

long long query(int L, int R) {
    l=L; r=R;
    ll atb=l*leaf;
    if(atb>r) atb+=(atb-r);
    return atb;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19