oj.uz

Submission #958474

# Submission time Handle Problem Language Result Execution time Memory
958474 2024-04-05T21:04:42 Z 876pol Closing Time (IOI23_closing) C++17
18 / 100
 1000 ms 45180 KB 
#include "closing.h"

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define TRAV(a, c) for (const auto &a : c)
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << '[';
    for (auto it = obj.begin(); it != obj.end(); it++)
        out << &", "[2 * (it == obj.begin())] << *it;
    return out << ']';
}

int max_score(int N, int X, int Y, ll K, vec<int> U, vec<int> V, vec<int> W) {
    vec<vec<pll>> graph(N);
    FOR(i, 0, N - 1) {
        graph[U[i]].push_back({V[i], W[i]});
        graph[V[i]].push_back({U[i], W[i]});
    }
    vec<bool> in_path(N);
    vec<pll> path;
    function<bool(ll, ll)> dfs1 = [&](ll curr, ll prev) -> bool {
        if (curr == Y) return true;
        TRAV(e, graph[curr]) {
            if (e.first == prev) continue;
            in_path[e.first] = 1;
            path.push_back({e.first, path.back().second + e.second});
            if (dfs1(e.first, curr)) return true;
            in_path[e.first] = 0;
            path.pop_back();
        }
        return false;
    };
    in_path[X] = 1;
    path.push_back({X, 0});
    dfs1(X, -1);
    ll length = path.back().second;
    ll M = path.size();
    vec<vec<ll>> dist(M);
    FOR(i, 0, M) {
        function<void(ll, ll, ll)> dfs2 = [&](ll curr, ll prev, ll cdist) {
            dist[i].push_back(cdist);
            TRAV(e, graph[curr]) {
                if (e.first == prev || in_path[e.first]) continue;
                dfs2(e.first, curr, cdist + e.second);
            }
        };
        dfs2(path[i].first, -1, 0);
        sort(dist[i].begin(), dist[i].end());
    }
    // dbg(in_path);
    // dbg(path);
    // dbg(dist);
    ll best = 0;
    FOR(x, 0, M) {
        FOR(y, 0, M) {
            // [0, x] and [y, M - 1]
            ll ans = 0;
            ll curr = 0;
            multiset<pair<ll, pll>> ms1, ms2;
            CFOR(i, 0, min(x, y - 1)) {
                ans++;
                curr += path[i].second;
                for (auto it = dist[i].begin() + 1; it != dist[i].end(); it++) {
                    ms1.insert({path[i].second + *it, {-1, -1}});
                }
            }
            CFOR(i, max(x + 1, y), M - 1) {
                ans++;
                curr += length - path[i].second;
                for (auto it = dist[i].begin() + 1; it != dist[i].end(); it++) {
                    ms1.insert({length - path[i].second + *it, {-1, -1}});
                }
            }
            CFOR(i, y, x) {
                ll mn = min(path[i].second, length - path[i].second);
                ll mx = max(path[i].second, length - path[i].second);
                ans += 2;
                curr += mx;
                for (auto it = dist[i].begin() + 1; it != dist[i].end(); it++) {
                    ms1.insert({mn + *it, {mn + *it, mx - mn}});
                    ms2.insert({mx + *it, {mn + *it, mx - mn}});
                }
            }
            if (curr > K) continue;
            // dbg(ms1);
            // dbg(ms2);
            // dbg(curr);
            // dbg(ans);
            while (ms1.size() || ms2.size()) {
                auto take1 = [&]() {
                    auto tmp = *ms1.begin();
                    if (tmp.second != pll{-1, -1}) {
                        ms2.erase(
                            ms2.find({tmp.second.first + tmp.second.second,
                                      tmp.second}));
                        ms1.insert({tmp.second.second, {-1, -1}});
                    }
                    ms1.erase(ms1.find(tmp));
                    ans += 1;
                    curr += tmp.first;
                };
                auto take2 = [&]() {
                    auto tmp = *ms2.begin();
                    ms1.erase(ms1.find({tmp.second.first, tmp.second}));
                    ms2.erase(ms2.find(tmp));
                    ans += 2;
                    curr += tmp.first;
                };
                if (ms1.size() == 1) {
                    if (ms2.size() && curr + ms2.begin()->first <= K) {
                        take2();
                    } else if (curr + ms1.begin()->first <= K) {
                        take1();
                    } else {
                        break;
                    }
                } else {
                    if (ms2.size() &&
                        ms1.begin()->first + next(ms1.begin())->first >=
                            ms2.begin()->first &&
                        curr + ms2.begin()->first <= K) {
                        take2();
                    } else if (curr + ms1.begin()->first <= K) {
                        take1();
                    } else {
                        break;
                    }
                }
            }
            // dbg(x);
            // dbg(y);
            // dbg(ans);
            best = max(best, ans);
        }
        // cerr << x << endl;
    }
    return best;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 45180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 428 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 428 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 7 ms 352 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Execution timed out 1059 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 428 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 7 ms 352 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Execution timed out 1059 ms 348 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 436 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 428 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 7 ms 352 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 600 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 436 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '41', found: '40'
39 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 428 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 7 ms 352 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Execution timed out 1059 ms 348 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 428 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 7 ms 352 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Execution timed out 1059 ms 348 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 428 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 7 ms 352 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 464 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Execution timed out 1059 ms 348 KB Time limit exceeded
23 Halted 0 ms 0 KB -