Submission #1039167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039167		RecursiveCo	Closing Time (IOI23_closing)	C++17	8 / 100	103 ms	35016 KiB

closing

// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long int

template <typename T, typename I>
struct segtree {
    int n;
    vector<T> tree;
    vector<I> initial;
    T id;

    segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) {
        tree.resize(4 * n);
    }

    T conquer(T left, T right) {
        // write your conquer function
    }

    T value(I inp) {
        // write your value function
    }

    void build(int v, int l, int r) {
        if (l == r) tree[v] = value(initial[l]);
        else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int v, int l, int r, int i, I x) {
        if (l == r) tree[v] = value(x);
        else {
            int middle = (l + r) / 2;
            if (middle >= i) upd(2 * v, l, middle, i, x);
            else upd(2 * v + 1, middle + 1, r, i, x);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    T query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        else if (r < ql || qr < l) return id;
        int middle = (l + r) / 2;
        T left = query(2 * v, l, middle, ql, qr);
        T right = query(2 * v + 1, middle + 1, r, ql, qr);
        return conquer(left, right);
    }
};

// vector<int>

vector<vector<pair<int, int>>> adjList;
vector<long long> fromX;
vector<long long> fromY;

void dfs(int v, int p, long long d, int which) {
    if (which) fromY[v] = d;
    else fromX[v] = d;
    for (auto pa: adjList[v]) {
        int con = pa.first;
        long long w = pa.second;
        if (con == p) continue;
        dfs(con, v, d + w, which);
    }
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    adjList.clear();
    adjList.resize(N);
    fromX.clear();
    fromX.resize(N);
    fromY.clear();
    fromY.resize(N);
    forto(N - 1, i) {
        int a = U[i];
        int b = V[i];
        int w = W[i];
        adjList[a].push_back({b, w});
        adjList[b].push_back({a, w});
    }
    dfs(X, -1, 0ll, 0);
    dfs(Y, -1, 0ll, 1);
    if (fromY[X] > 2 * K) {
        vector<long long> paths;
        forto(N, i) {
            paths.push_back(min(fromX[i], fromY[i]));
        }
        sortl(paths);
        int ans = 0;
        long long sum = 0;
        forto(N, i) {
            if (sum + paths[i] > K) break;
            sum += paths[i];
            ans++;
        }
        return ans;
    } else {
        // assumption: path
        // case 1: everything in between contributes twice.
        long long C = fromX[Y]; // = fromY[X]
        long long sum1 = 0ll;
        int ans = 0;
        int ans1 = 0;
        vector<long long> far;
        forto(N, i) {
            int val = max(fromX[i], fromY[i]);
            if (val < C) sum1 += val, ans1 += 2;
            else far.push_back(min(fromX[i], fromY[i]));
        }
        int s = far.size();
        if (sum1 <= K) {
            sortl(far);
            long long left = K - sum1;
            
            ans = max(ans, ans1);
            long long farsum = 0;
            forto(s, i) {
                farsum += far[i];
                if (farsum > left) break;
                long long extra = (left - farsum) / C;
                int extraint = extra > (long long) (i + 1)? i + 1: (int) extra;
                ans = max(ans, ans1 + (i + 1) + extraint);
            }
        }

        vector<pair<long long, int>> middle;
        forto(N, i) {
            int val = max(fromX[i], fromY[i]);
            if (val < C) middle.push_back({fromX[i], i});
        }
        sortl(middle);
        int midsz = middle.size();

        int ans2 = 0;
        far.push_back(0);
        s++;
        sortl(far);
        long long sum2 = 0ll;
        forto(s, i) {
            sum2 += far[i];
            if (sum2 > K) break;
            long long left = K - sum2;
            forto(midsz + 1, l) {
                long long taken = 0ll;
                for (int r = l; r <= midsz; r++) {
                    if (r != midsz) taken += max(middle[r].first, fromY[middle[r].second]);
                    if (taken > left) break;
                    vector<long long> once;
                    forto(l, j) once.push_back(min(middle[j].first, fromY[middle[j].second]));
                    for (int j = r + 1; j < midsz; j++) once.push_back(min(middle[j].first, fromY[middle[j].second]));
                    sortl(once);
                    long long remain = left - taken;
                    int o = once.size();
                    int here = 0;
                    forto(o, i) {
                        if (remain < once[i]) break;
                        here++;
                        remain -= once[i];
                    }
                    ans2 = max(ans2, (i + 1) + 2 * (r == midsz? r - l: r - l + 1) + here - 1);
                    if (ans2 == 4) out(l), out(r);
                }
            }
        }
        ans = max(ans, ans2);
        return ans;
    }
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:93:5: note: in expansion of macro 'forto'
   93 |     forto(N - 1, i) {
      |     ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:104:9: note: in expansion of macro 'forto'
  104 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:110:9: note: in expansion of macro 'forto'
  110 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:124:9: note: in expansion of macro 'forto'
  124 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:136:13: note: in expansion of macro 'forto'
  136 |             forto(s, i) {
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:146:9: note: in expansion of macro 'forto'
  146 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:158:9: note: in expansion of macro 'forto'
  158 |         forto(s, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'l' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:162:13: note: in expansion of macro 'forto'
  162 |             forto(midsz + 1, l) {
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:168:21: note: in expansion of macro 'forto'
  168 |                     forto(l, j) once.push_back(min(middle[j].first, fromY[middle[j].second]));
      |                     ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:174:21: note: in expansion of macro 'forto'
  174 |                     forto(o, i) {
      |                     ^~~~~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17