Submission #823468

#	Time	Username	Problem	Language	Result	Execution time	Memory
823468		SUNWOOOOOOOO	Two Currencies (JOI23_currencies)	C++17	100 / 100	1648 ms	55716 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pint = pair <int, int>;
const int mxN = 100005, SIZE = 200000;
vector <int> adj[mxN], mid[mxN];
int n, m, q, A[mxN], B[mxN], S[mxN], T[mxN], X[mxN], ans[mxN]; LL Y[mxN];
int tin[2 * mxN], tout[2 * mxN], tcnt = 0, low[mxN], high[mxN], L[mxN];
pint C[mxN];

struct lca {
    int par[20][mxN], dep[mxN];
    void dfs(int now, int p){
        par[0][now] = p;
        for (int chi : adj[now]){
            if (chi == p) continue;
            dep[chi] = dep[now] + 1; 
            dfs(chi, now);
        }
    }
    void init(){
        dfs(1, 1);
        for (int i = 1; i < 20; i++){
            for (int j = 1; j <= n; j++){
                par[i][j] = par[i - 1][par[i - 1][j]];
            }
        }
    }
    int query(int x, int y){
        if (dep[x] < dep[y]) swap(x, y);
        int dif = dep[x] - dep[y];
        for (int i = 0; dif; i++){
            if (dif & 1) x = par[i][x];
            dif /= 2;
        }
        for (int i = 19; i >= 0; i--){
            if (par[i][x] != par[i][y]){
                x = par[i][x], y = par[i][y];
            }
        }
        if (x == y) return x;
        else return par[0][x];
    }
} lca;

struct segtree {
    LL node[8 * mxN];
    void init(){
        memset(node, 0, sizeof node);
    }
    void update(int x, int val){
        for (x += 2 * n; x > 0; x /= 2) node[x] += val;
    }
    LL query(int L, int R){
        LL ret = 0;
        for (L += 2 * n, R += 2 * n; L <= R; L /= 2, R /= 2){
            if (L % 2 == 1) ret += node[L++];
            if (R % 2 == 0) ret += node[R--];
        }
        return ret;
    }
} tree1, tree2;

void euler_tour(int now, int p)
{
    tin[now] = ++tcnt;
    for (int elm : adj[now]){
        if (elm == p) continue;
        euler_tour(elm, now);
    }
    tout[now] = ++tcnt;
}

int main()
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n - 1; i++){
        scanf("%d %d", &A[i], &B[i]);
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    for (int i = 1; i <= m; i++) scanf("%d %d", &C[i].second, &C[i].first);
    for (int i = 1; i <= q; i++) scanf("%d %d %d %lld", &S[i], &T[i], &X[i], &Y[i]);

    lca.init();
    euler_tour(1, 1);
    sort(C + 1, C + m + 1); // {silver no, road no}
    for (int i = 1; i <= q; i++){low[i] = 0, high[i] = m;}
    for (int i = 1; i <= q; i++){
        L[i] = lca.query(S[i], T[i]);
    }
    for (int i = 1; i <= n - 1; i++){
        if (lca.dep[A[i]] < lca.dep[B[i]]) swap(A[i], B[i]);
    }
    memset(ans, -1, sizeof ans);

    while (1){
        tree1.init();
        tree2.init();
        for (int i = 0; i <= m; i++) mid[i].clear();
        bool endflag = true;
        for (int i = 1; i <= q; i++){
            if (low[i] <= high[i]){
                endflag = false;
                mid[(low[i] + high[i]) / 2].push_back(i);
            }
        }
        if (endflag) break;

        for (int i = 0; i <= m; i++){
            for (int j : mid[i]){ // ansi = maximum no of gold replaced by silver
                LL ysum = tree2.query(1, tin[T[j]]) + tree2.query(1, tin[S[j]]) - 2 * tree2.query(1, tin[L[j]]);
                if (ysum <= Y[j]){
                    ans[j] = tree1.query(1, tin[T[j]]) + tree1.query(1, tin[S[j]]) - 2 * tree1.query(1, tin[L[j]]);
                    low[j] = i + 1;
                }
                else {
                    high[j] = i - 1;
                }
            }

            if (i == m) continue;
            int a = A[C[i + 1].second], val = C[i + 1].first;
            tree1.update(tin[a], 1);
            tree1.update(tout[a], -1);
            tree2.update(tin[a], val);
            tree2.update(tout[a], -val);
        }
    }

    tree1.init();
    for (int i = 1; i <= m; i++){
        int a = A[C[i].second], val = C[i].first;
        tree1.update(tin[a], 1);
        tree1.update(tout[a], -1);
    }

    for (int i = 1; i <= q; i++) {
        int gsum = tree1.query(1, tin[T[i]]) + tree1.query(1, tin[S[i]]) - 2 * tree1.query(1, tin[L[i]]);
        if (X[i] + ans[i] >= gsum) printf("%d\n", max(0, X[i] + ans[i] - gsum));
        else printf("-1\n");
    }

    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:133:33: warning: unused variable 'val' [-Wunused-variable]
  133 |         int a = A[C[i].second], val = C[i].first;
      |                                 ^~~
currencies.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d %d", &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:82:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     for (int i = 1; i <= m; i++) scanf("%d %d", &C[i].second, &C[i].first);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:83:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     for (int i = 1; i <= q; i++) scanf("%d %d %d %lld", &S[i], &T[i], &X[i], &Y[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32