|

General

# Author Problem Lang Verdict Time Memory Sent Judged
170876140 Practice:
nk3
1714G - 25 GNU C++17 Wrong answer on test 4 124 ms 15460 KB 2022-09-04 20:06:24 2022-09-04 20:06:24
→ Source
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define rev(i, n) for(int i = (n)-1; i >= 0; i--)
#define repm(i, m, n) for(int i = (m); i < (n); i++)
#define revm(i, m, n) for(int i = (m)-1; i >= n; i--)
typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;
const ll INF = 1E9 + 7;

ll lcm(ll a, ll b) {
return a / __gcd(a, b) * b;
}

vi gv(int n) {
vi v(n);
rep(i, n) cin >> v[i];
return v;
}

const int N = 2e5 + 4;
bool state[N];
int a[N], b[N], q[N];

void dfs(int i, vvi& v, vi& w, int s) {
if(state[i]) return;
state[i] = true;

if(i != 1) {
w.push_back(w.back() + b[i]);
s += a[i];
q[i] = lower_bound(w.begin(), w.end(), s+1) - w.begin() - 1;
}

for(auto k : v[i]) {
dfs(k, v, w, s);
}

w.pop_back();
}

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

vvi v(n+1);

repm(i, 2, n+1) {
int p;
cin >> p >> a[i] >> b[i];
v[p].push_back(i);
}

rep(i, n+1) state[i] = false;
vi w(1);
dfs(1, v, w, 0);

repm(i, 2, n+1) cout << q[i] << " ";
cout << "\n";
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int t = 1;
cin >> t;
while(t--) {
test_case();
}
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?