#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 4e5 + 10;
ll n;
vector<ll> s, p, w, l;
vector<ll> win;
ll g[N], start_time[N], tme = 0;
bool subtask2, vis[N];
set<vector<ll>> st;
void dfs(ll v){
vis[v] = 1;
start_time[v] = tme;
st.insert({s[v], tme, v});
tme++;
if (!vis[w[v]])
dfs(w[v]);
auto ub = st.upper_bound({2 * s[v], -1, -1});
if (ub == st.end())
g[v] = -1;
else
g[v] = (*ub)[2];
st.erase({s[v], start_time[v], v});
}
void init(int inp_n, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
n = inp_n;
for (ll x : S)
s.push_back(x);
for (ll x : P)
p.push_back(x);
for (ll x : W)
w.push_back(x);
for (ll x : L)
l.push_back(x);
memset(g, -1, sizeof g);
win.resize(n + 1, 0);
for (ll i = n - 1; i >= 0; i--){
if (w[i] == n)
win[i] = s[i];
else
win[i] = s[i] + win[w[i]];
}
for (ll i = 0; i < n; i ++){
if (!vis[i]) dfs(i);
}
subtask2 = 1;
for (ll i=0; i<n; i++)
subtask2 &= (s[i] == p[i]);
}
ll simulate(int x, int z){
if (subtask2){
ll cur_node = x;
ll cur_strength = z;
while (cur_node != n){
if (s[cur_node] > cur_strength){
cur_strength += p[cur_node];
cur_node = l[cur_node];
}
else{
ll u = g[cur_node];
if (u == -1){
cur_strength += win[cur_node];
break;
}
cur_strength += win[cur_node] - win[u];
cur_node = u;
}
}
return cur_strength;
}
ll cur_strength = z;
while (x != n){
int opp = s[x];
if (opp > cur_strength){
cur_strength += p[x];
x = l[x];
}
else{
cur_strength += s[x];
x = w[x];
}
}
return cur_strength;
}
// int main(){
// int n, q;
// cin >> n >> q;
// vector<int> s(n), p(n), w(n), l(n);
// for (int i = 0; i < n; i ++) cin >> s[i];
// for (int i = 0; i < n; i ++) cin >> p[i];
// for (int i = 0; i < n; i ++) cin >> w[i];
// for (int i = 0; i < n; i ++) cin >> l[i];
// init(n, s, p, w, l);
// while (q--){
// int x, z;
// cin >> x >> z;
// cout << simulate(x, z) << endl;
// }
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4952 KB |
Output is correct |
3 |
Correct |
3 ms |
4956 KB |
Output is correct |
4 |
Correct |
22 ms |
9968 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
23 ms |
9808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
38 ms |
11336 KB |
Output is correct |
3 |
Correct |
2098 ms |
18120 KB |
Output is correct |
4 |
Correct |
2459 ms |
20832 KB |
Output is correct |
5 |
Correct |
1657 ms |
17352 KB |
Output is correct |
6 |
Execution timed out |
7042 ms |
11100 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
38 ms |
11336 KB |
Output is correct |
3 |
Correct |
2098 ms |
18120 KB |
Output is correct |
4 |
Correct |
2459 ms |
20832 KB |
Output is correct |
5 |
Correct |
1657 ms |
17352 KB |
Output is correct |
6 |
Execution timed out |
7042 ms |
11100 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
38 ms |
11336 KB |
Output is correct |
3 |
Correct |
2098 ms |
18120 KB |
Output is correct |
4 |
Correct |
2459 ms |
20832 KB |
Output is correct |
5 |
Correct |
1657 ms |
17352 KB |
Output is correct |
6 |
Execution timed out |
7042 ms |
11100 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |