# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1064607 |
2024-08-18T15:31:16 Z |
Misha_Yuzvik |
Jobs (BOI24_jobs) |
C++14 |
|
2000 ms |
73048 KB |
# include <bits/stdc++.h>
using namespace std;
# define For(i , l , r) for(long long i = (l); i <= (r); i++)
# define Rep(i , n) For(i , 0 , (n) - 1)
# define size(x) (long long)x.size()
# define MAXN 500005
# define MAXK 1000005
# define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll inf = 1e7 + 7;
const ll mod = 1e9 + 9;
const ld eps = 0.0000001;
ll n , m , K , ans = 0 , q , finish;
vector<vector<ll> >g(MAXN);
vector<ll>val(MAXN);
vector<ll>root(MAXN);
multiset<pair<ll , ll> >stv[MAXN];
void init(ll N) {
For (i , 0 , N) {
root[i] = i;
}
}
ll get_r(ll x) {
if (root[x] == x) return x;
else return root[x] = get_r(root[x]);
}
void check(multiset<pair<ll , ll> >&st) {
ll prev = -1e18;
for (auto it = st.begin(); it != st.end(); it++) {
if (it->first < prev) assert(0);
if (it->first < 0 || it->second < 0) assert(0);
prev = it->second;
}
}
void insert_pair(multiset<pair<ll , ll> >&st , ll ai , ll bi) {
if (size(st) == 0) {
st.insert({ai , bi});
return;
}
auto it = st.lower_bound({ai , -1e18});
auto itl = it , itr = it;
if (it != st.begin()) {
it--;
if (it->second >= ai) {
itl = it;
bi = bi - ai + it->second;
ai = it->first; // kurwa
}
it++;
}
while (it != st.end() && it->first <= bi) {
bi = bi - it->first + it->second;
it++;
}
itr = it;
if (itl != itr) st.erase(itl , itr);
st.insert({ai , bi});
check(st);
}
ll Union(ll x , ll y) {
ll r1 = get_r(x) , r2 = get_r(y);
if (r1 == r2) assert(0);
if (size(stv[r1]) > size(stv[r2])) swap(r1 , r2);
root[r2] = r1;
auto& st = stv[r1];
for (auto [ai , bi] : stv[r2]) {
insert_pair(st , ai , bi);
}
return r1;
}
void dfs(ll v , ll p) {
pair<ll , ll>cur;
if (val[v] < 0) cur = {abs(val[v]) , 0};
else cur = {0 , val[v]};
ll rv = -1;
for (auto to : g[v]) {
if (to == p) continue;
dfs(to , v);
if (rv == -1) rv = get_r(to);
else rv = Union(rv , to);
}
if (rv == -1) {
if (val[v] > 0) {
insert_pair(stv[v] , cur.first , cur.second);
}
return;
}
auto &st = stv[rv];
root[v] = rv;
if (val[v] > 0) {
insert_pair(st , cur.first , cur.second);
} else if (val[v] < 0) {
while (size(st) > 0 && cur.first >= cur.second) {
auto [a1 , b1] = *st.begin();
cur.first = cur.first - cur.second + a1;
cur.second = b1;
st.erase(st.begin());
}
if (cur.first < cur.second) insert_pair(st , cur.first , cur.second);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll val0;
cin >> n >> val0;
For (i , 1 , n) {
ll p;
cin >> val[i] >> p;
g[i].push_back(p);
g[p].push_back(i);
}
val[0] = val0;
// For (i , 1 , n) cin >> val[i];
// Rep (i , n - 1) {
// ll u , v;
// cin >> u >> v;
// g[u].push_back(v);
// g[v].push_back(u);
// }
// n++;
// val[n] = 1e18;
// g[n].push_back(finish);
// g[finish].push_back(n);
init(n);
dfs(0 , -1);
auto& wyn = stv[get_r(0)];
ll sum = 0;
for (auto [ai , bi] : wyn) {
if (sum >= ai) sum = sum - ai + bi;
// cerr << ai << ' ' << bi << "\n";
}
cout << sum - val0;
// cerr << 1 << endl;
// if (sum >= 1e17) cout << "TAK";
// else cout << "NIE";
}
Compilation message
Main.cpp: In function 'll Union(ll, ll)':
Main.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for (auto [ai , bi] : stv[r2]) {
| ^
Main.cpp: In function 'void dfs(ll, ll)':
Main.cpp:95:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
95 | auto [a1 , b1] = *st.begin();
| ^
Main.cpp: In function 'int main()':
Main.cpp:130:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
130 | for (auto [ai , bi] : wyn) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2047 ms |
73048 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
43356 KB |
Output is correct |
2 |
Correct |
15 ms |
43352 KB |
Output is correct |
3 |
Correct |
15 ms |
43484 KB |
Output is correct |
4 |
Correct |
91 ms |
50260 KB |
Output is correct |
5 |
Correct |
21 ms |
43608 KB |
Output is correct |
6 |
Correct |
17 ms |
43612 KB |
Output is correct |
7 |
Correct |
18 ms |
43652 KB |
Output is correct |
8 |
Correct |
28 ms |
44368 KB |
Output is correct |
9 |
Correct |
118 ms |
52752 KB |
Output is correct |
10 |
Correct |
67 ms |
48584 KB |
Output is correct |
11 |
Correct |
17 ms |
43608 KB |
Output is correct |
12 |
Correct |
17 ms |
43540 KB |
Output is correct |
13 |
Correct |
17 ms |
43612 KB |
Output is correct |
14 |
Correct |
21 ms |
44152 KB |
Output is correct |
15 |
Correct |
71 ms |
50260 KB |
Output is correct |
16 |
Correct |
51 ms |
47952 KB |
Output is correct |
17 |
Correct |
18 ms |
43612 KB |
Output is correct |
18 |
Correct |
17 ms |
43612 KB |
Output is correct |
19 |
Correct |
20 ms |
43724 KB |
Output is correct |
20 |
Correct |
23 ms |
43864 KB |
Output is correct |
21 |
Correct |
57 ms |
49108 KB |
Output is correct |
22 |
Correct |
34 ms |
46668 KB |
Output is correct |
23 |
Correct |
17 ms |
43800 KB |
Output is correct |
24 |
Correct |
16 ms |
43636 KB |
Output is correct |
25 |
Correct |
20 ms |
43612 KB |
Output is correct |
26 |
Correct |
20 ms |
43856 KB |
Output is correct |
27 |
Correct |
50 ms |
48336 KB |
Output is correct |
28 |
Correct |
18 ms |
43612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
43356 KB |
Output is correct |
2 |
Correct |
15 ms |
43352 KB |
Output is correct |
3 |
Correct |
15 ms |
43484 KB |
Output is correct |
4 |
Correct |
91 ms |
50260 KB |
Output is correct |
5 |
Correct |
21 ms |
43608 KB |
Output is correct |
6 |
Correct |
17 ms |
43612 KB |
Output is correct |
7 |
Correct |
18 ms |
43652 KB |
Output is correct |
8 |
Correct |
28 ms |
44368 KB |
Output is correct |
9 |
Correct |
118 ms |
52752 KB |
Output is correct |
10 |
Correct |
67 ms |
48584 KB |
Output is correct |
11 |
Correct |
17 ms |
43608 KB |
Output is correct |
12 |
Correct |
17 ms |
43540 KB |
Output is correct |
13 |
Correct |
17 ms |
43612 KB |
Output is correct |
14 |
Correct |
21 ms |
44152 KB |
Output is correct |
15 |
Correct |
71 ms |
50260 KB |
Output is correct |
16 |
Correct |
51 ms |
47952 KB |
Output is correct |
17 |
Correct |
18 ms |
43612 KB |
Output is correct |
18 |
Correct |
17 ms |
43612 KB |
Output is correct |
19 |
Correct |
20 ms |
43724 KB |
Output is correct |
20 |
Correct |
23 ms |
43864 KB |
Output is correct |
21 |
Correct |
57 ms |
49108 KB |
Output is correct |
22 |
Correct |
34 ms |
46668 KB |
Output is correct |
23 |
Correct |
17 ms |
43800 KB |
Output is correct |
24 |
Correct |
16 ms |
43636 KB |
Output is correct |
25 |
Correct |
20 ms |
43612 KB |
Output is correct |
26 |
Correct |
20 ms |
43856 KB |
Output is correct |
27 |
Correct |
50 ms |
48336 KB |
Output is correct |
28 |
Correct |
18 ms |
43612 KB |
Output is correct |
29 |
Execution timed out |
2025 ms |
72788 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
43356 KB |
Output is correct |
2 |
Correct |
15 ms |
43352 KB |
Output is correct |
3 |
Correct |
15 ms |
43484 KB |
Output is correct |
4 |
Correct |
91 ms |
50260 KB |
Output is correct |
5 |
Correct |
21 ms |
43608 KB |
Output is correct |
6 |
Correct |
17 ms |
43612 KB |
Output is correct |
7 |
Correct |
18 ms |
43652 KB |
Output is correct |
8 |
Correct |
28 ms |
44368 KB |
Output is correct |
9 |
Correct |
118 ms |
52752 KB |
Output is correct |
10 |
Correct |
67 ms |
48584 KB |
Output is correct |
11 |
Correct |
17 ms |
43608 KB |
Output is correct |
12 |
Correct |
17 ms |
43540 KB |
Output is correct |
13 |
Correct |
17 ms |
43612 KB |
Output is correct |
14 |
Correct |
21 ms |
44152 KB |
Output is correct |
15 |
Correct |
71 ms |
50260 KB |
Output is correct |
16 |
Correct |
51 ms |
47952 KB |
Output is correct |
17 |
Correct |
18 ms |
43612 KB |
Output is correct |
18 |
Correct |
17 ms |
43612 KB |
Output is correct |
19 |
Correct |
20 ms |
43724 KB |
Output is correct |
20 |
Correct |
23 ms |
43864 KB |
Output is correct |
21 |
Correct |
57 ms |
49108 KB |
Output is correct |
22 |
Correct |
34 ms |
46668 KB |
Output is correct |
23 |
Correct |
17 ms |
43800 KB |
Output is correct |
24 |
Correct |
16 ms |
43636 KB |
Output is correct |
25 |
Correct |
20 ms |
43612 KB |
Output is correct |
26 |
Correct |
20 ms |
43856 KB |
Output is correct |
27 |
Correct |
50 ms |
48336 KB |
Output is correct |
28 |
Correct |
18 ms |
43612 KB |
Output is correct |
29 |
Correct |
16 ms |
43356 KB |
Output is correct |
30 |
Correct |
18 ms |
43816 KB |
Output is correct |
31 |
Correct |
19 ms |
43876 KB |
Output is correct |
32 |
Correct |
24 ms |
44356 KB |
Output is correct |
33 |
Correct |
74 ms |
49484 KB |
Output is correct |
34 |
Correct |
66 ms |
48980 KB |
Output is correct |
35 |
Correct |
19 ms |
43612 KB |
Output is correct |
36 |
Correct |
17 ms |
43700 KB |
Output is correct |
37 |
Correct |
20 ms |
43916 KB |
Output is correct |
38 |
Correct |
20 ms |
44124 KB |
Output is correct |
39 |
Correct |
55 ms |
48724 KB |
Output is correct |
40 |
Correct |
41 ms |
46672 KB |
Output is correct |
41 |
Correct |
16 ms |
43612 KB |
Output is correct |
42 |
Correct |
18 ms |
43612 KB |
Output is correct |
43 |
Correct |
17 ms |
43868 KB |
Output is correct |
44 |
Correct |
28 ms |
44380 KB |
Output is correct |
45 |
Correct |
43 ms |
47760 KB |
Output is correct |
46 |
Correct |
28 ms |
46172 KB |
Output is correct |
47 |
Correct |
16 ms |
43868 KB |
Output is correct |
48 |
Correct |
17 ms |
43612 KB |
Output is correct |
49 |
Correct |
18 ms |
43944 KB |
Output is correct |
50 |
Correct |
21 ms |
43868 KB |
Output is correct |
51 |
Correct |
46 ms |
47696 KB |
Output is correct |
52 |
Correct |
21 ms |
44376 KB |
Output is correct |
53 |
Correct |
19 ms |
43868 KB |
Output is correct |
54 |
Correct |
22 ms |
43868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2047 ms |
73048 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |