Submission #625127

#	Time	Username	Problem	Language	Result	Execution time	Memory
625127		MohamedFaresNebili	Construction of Highway (JOI18_construction)	C++14	100 / 100	382 ms	114088 KiB

construction

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
            #define int ll

            const int MOD = 998244353;

            int N, timer, C[100005], X[100005], Y[100005];
            int tin[100005], dep[100005], S[100005], T[100005];
            vector<int> adj[100005]; deque<pair<int, int>> sub[100005];
            int P[400005], ST[400005];

            int dfs_size(int v, int p) {
                P[v] = p; dep[v] = dep[p] + 1; S[v] = 1;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    S[v] += dfs_size(u, v);
                }
                return S[v];
            }
            void getHeavy(int v, int p, int top) {
                tin[v] = timer++; T[v] = top;
                int heavy = -1, cur = 0;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    if(S[u] > cur)
                        cur = S[u], heavy = u;
                }
                if(heavy == -1) return;
                getHeavy(heavy, v, top);
                for(auto u : adj[v]) {
                    if(u == p || u == heavy) continue;
                    getHeavy(u, v, u);
                }
            }
            int _N;
            void init(int n) {
                _N = n;
                for(int l = 0; l <= _N; l++) ST[l] = 0;
            }
            void update(int p, int v) {
                for(; p <= _N; p += (p & (-p)))
                    ST[p] += v;
            }
            int query(int p) {
                int res = 0;
                for(; p; p -= (p & (-p)))
                    res += ST[p];
                return res;
            }
            int solve(int v) {
                vector<pair<int, int>> E; vector<int> comp;
                while(v != -1) {
                    int top = T[v];
                    int d = dep[v] - dep[top] + 1;
                    vector<pair<int, int>> A;
                    for(int i = 0; i < sub[top].size(); i++) {
                        int k = sub[top][i].first; int cur = sub[top][i].second;
                        if(k <= d) {
                            A.push_back({k, cur});
                            d -= k; continue;
                        }
                        A.push_back({d, cur});
                        break;
                    }
                    for(int l = A.size() - 1; ~l; l--) {
                        E.push_back(A[l]); comp.push_back(A[l].second);
                    }
                    v = P[top];
                }
                reverse(E.begin(), E.end());
                sort(comp.begin(), comp.end());
                comp.erase(unique(comp.begin(), comp.end()), comp.end());
                int ans = 0, tot = 0; init(comp.size());
                for(auto u : E) {
                    u.second = lower_bound(comp.begin(), comp.end(), u.second) - comp.begin();
                    ans += u.first * (tot - query(++u.second ));
                    tot += u.first;
                    update(u.second, u.first);
                }
                return ans;
            }
            void add(int v, int cur) {
                while(v != -1) {
                    int top = T[v], d = dep[v] - dep[top] + 1;
                    while(!sub[top].empty()) {
                        int k = sub[top][0].first;
                        if(k <= d) {
                            sub[top].pop_front();
                            d -= k; continue;
                        }
                        sub[top].front().first -= d;
                        break;
                    }
                    sub[top].push_front({dep[v] - dep[top] + 1, cur});
                    v = P[top];
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N;
                for(int l = 1; l <= N; l++)
                    cin >> C[l];
                for(int l = 0; l < N - 1; l++) {
                    cin >> X[l] >> Y[l];
                    adj[X[l]].push_back(Y[l]);
                    adj[Y[l]].push_back(X[l]);
                }
                dep[1] = -1; dfs_size(1, 1); getHeavy(1, 1, 1);
                P[1] = -1; add(1, C[1]);
                for(int l = 0; l < N - 1; l++) {
                    int U = X[l], V = Y[l];
                    cout << solve(U) << "\n";
                    add(V, C[V]);
                }
                return 0;
            }

Compilation message (stderr)

construction.cpp: In function 'll solve(ll)':
construction.cpp:69:38: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                     for(int i = 0; i < sub[top].size(); i++) {
      |                                    ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84