oj.uz

Submission #885906

# Submission time Handle Problem Language Result Execution time Memory
885906 2023-12-11T02:57:11 Z abysmal Two Currencies (JOI23_currencies) C++14
100 / 100
 919 ms 41948 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>
#include<chrono>
#include<bitset>

using namespace std;
using namespace std::chrono;

const int64_t INF = (int64_t) 1e18 + 100;
const int64_t mINF = (int64_t) 2 * 1e9 + 5;
const int64_t MOD = (int64_t) 20230401;
const int64_t MOD2 = 998244353;
const int nbit = 63;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};

struct Query
{
    int s;
    int t;
    int64_t x;
    int64_t y;

    Query(int s_, int t_, int64_t x_, int64_t y_) : s(s_), t(t_), x(x_), y(y_) {}
};

struct Path
{
    int u;
    int w;

    Path(int u_, int w_) : u(u_), w(w_) {}

    bool operator < (const Path& o) const
    {
        return w < o.w;
    }
};

struct Solution
{
    int n;
    int m;
    int q;
    int t;
    int k;
    int LOG;
    vector<int> f;
    vector<int> pos;
    vector<int> tin;
    vector<int> tout;
    vector<int> depth;
    vector<Path> path;
    vector<vector<int> > rmq;
    vector<vector<int> > adj;
    Solution() {}

    void solve()
    {
        cin >> n >> m >> q;

        t = 1; k = 0;
        f.resize(n);
        tin.resize(n, 0);
        tout.resize(n, 0);
        depth.resize(n, 0);
        adj.resize(n);
        vector<pair<int, int> > edges;
        for(int i = 0; i < n - 1; i++)
        {
            int u; int v;
            cin >> u >> v;
            u--; v--;

            edges.emplace_back(u, v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        DFS();
        LOG = 0;
        while(MASK(LOG) <= k) LOG++;
        rmq.resize(LOG, vector<int>(k, 0));
        for(int i = 0; i < k; i++)
        {
            rmq[0][i] = pos[i];
        }

        for(int i = 1; i < LOG; i++)
        {
            for(int j = 0; j + MASK(i) - 1 < k; j++)
            {
                int d1 = depth[ rmq[i - 1][j] ];
                int d2 = depth[ rmq[i - 1][j + MASK(i - 1)] ];

                if(d1 < d2) rmq[i][j] = rmq[i - 1][j];
                else rmq[i][j] = rmq[i - 1][j + MASK(i - 1)];
            }
        }

        for(int i = 0; i < m; i++)
        {
            int id; int c;
            cin >> id >> c;

            id--;
            int u = edges[id].first;
            int v = edges[id].second;
            if(depth[u] > depth[v]) swap(u, v);
            path.emplace_back(v, c);
        }

        sort(path.begin(), path.end());
        vector<Query> qury;
        for(int i = 0; i < q; i++)
        {
            int s; int e; int64_t x; int64_t y;
            cin >> s >> e >> x >> y;
            s--; e--;

            qury.emplace_back(s, e, x, y);
        }

        vector<int64_t> gold(t + 1, 0);
        vector<int64_t> silver(t + 1, 0);
        vector<int> l(q, 0);
        vector<int> r(q, m);
        vector<int> ans(q, -1);

        while(true)
        {
            fill(gold.begin(), gold.end(), 0);
            fill(silver.begin(), silver.end(), 0);
            for(int i = 0; i < m; i++)
            {
                int u = path[i].u;

                update(tin[u], 1, gold);
                update(tout[u], -1, gold);
            }
            vector<pair<int, int> > mid;
            for(int i = 0; i < q; i++)
            {
                if(l[i] > r[i]) continue;
                int md = l[i] + (r[i] - l[i]) / 2;
                mid.emplace_back(md, i);
            }
            if((int) mid.size() == 0) break;
            sort(mid.begin(), mid.end());
            int id = 0;
            for(int i = 0; i < m; i++)
            {
                while(id < (int) mid.size() && mid[id].first == i)
                {
                    int j = mid[id].second;
                    int s = qury[j].s; int e = qury[j].t; int64_t x = qury[j].x; int64_t y = qury[j].y;
                    int lca = LCA(s, e);

                    int64_t sums = sum(tin[s], silver) + sum(tin[e], silver) - 2 * sum(tin[lca], silver);
                    int64_t sumg = sum(tin[s], gold) + sum(tin[e], gold) - 2 * sum(tin[lca], gold);

                    if(x >= sumg && y >= sums)
                    {
                        ans[j] = x - sumg;
                        l[j] = mid[id].first + 1;
                    }
                    else if(x < sumg) l[j] = mid[id].first + 1;
                    else if(y < sums) r[j] = mid[id].first - 1;

                    id++;
                }

                int u = path[i].u;
                int w = path[i].w;
                update(tin[u], -1, gold); update(tout[u], 1, gold);
                update(tin[u], w, silver); update(tout[u], -w, silver);
            }

            while(id < (int) mid.size())
            {
                int j = mid[id].second;
                int s = qury[j].s; int e = qury[j].t; int64_t x = qury[j].x; int64_t y = qury[j].y;
                int lca = LCA(s, e);

                int64_t sums = sum(tin[s], silver) + sum(tin[e], silver) - 2 * sum(tin[lca], silver);
                int64_t sumg = sum(tin[s], gold) + sum(tin[e], gold) - 2 * sum(tin[lca], gold);

                if(x >= sumg && y >= sums)
                {
                    ans[j] = x - sumg;
                    l[j] = mid[id].first + 1;
                }
                else if(x < sumg) l[j] = mid[id].first + 1;
                else if(y < sums) r[j] = mid[id].first - 1;

                id++;
            }
        }

        for(int i = 0; i < q; i++)
        {
            cout << ans[i] << "\n";
        }
    }

    int LCA(int i, int j)
    {
        i = f[i]; j = f[j];
        if(i > j) swap(i, j);
        int len = j - i + 1;
        int kk = 31 - __builtin_clz(len);
        if(depth[ rmq[kk][i] ] < depth[ rmq[kk][j - MASK(kk) + 1] ]) return rmq[kk][i];
        return rmq[kk][j - MASK(kk) + 1];
    }

    void DFS(int u = 0, int p = -1)
    {
        f[u] = k++;
        tin[u] = t++;
        pos.push_back(u);
        for(int i = 0; i < (int) adj[u].size(); i++)
        {
            int v = adj[u][i];
            if(v == p) continue;

            depth[v] = depth[u] + 1;
            DFS(v, u);

            pos.push_back(u);
            k++;
        }

        tout[u] = t++;
    }

    void update(int i, int64_t val, vector<int64_t>& bit)
    {
        while(i < (int) bit.size())
        {
            bit[i] += val;
            i += i & (-i);
        }
    }

    int64_t sum(int i, vector<int64_t>& bit)
    {
        int64_t ans = 0;
        while(i > 0)
        {
            ans += bit[i];
            i -= i & (-i);
        }
        return ans;
    }

    int modadd(int t1, int t2)
    {
        int res = t1 + t2;
        if(res >= MOD) res -= MOD;
        return res;
    }

    int modsub(int t1, int t2)
    {
        int res = t1 - t2;
        if(res < 0) res += MOD;
        return res;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int64_t Abs(int64_t t1)
    {
        if(t1 < 0) return -t1;
        return t1;
    }

    int64_t MASK(int j)
    {
        return (1LL << j);
    }

    bool BIT(int64_t t1, int j)
    {
        return (t1 & MASK(j));
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();
//        auto start = high_resolution_clock::now();
    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }

//    auto stop = high_resolution_clock::now();
//    auto duration = duration_cast<microseconds>(stop - start);
//    cerr << duration.count() << "\n";
    return 0;
}

Subtask #1
10.0 / 10.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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 968 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 7 ms 1104 KB Output is correct
9 Correct 7 ms 1112 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 7 ms 1104 KB Output is correct
12 Correct 7 ms 1064 KB Output is correct
13 Correct 7 ms 980 KB Output is correct
14 Correct 7 ms 1116 KB Output is correct
15 Correct 7 ms 1064 KB Output is correct
16 Correct 7 ms 1024 KB Output is correct
17 Correct 7 ms 1116 KB Output is correct
18 Correct 7 ms 1116 KB Output is correct
19 Correct 7 ms 860 KB Output is correct
20 Correct 6 ms 860 KB Output is correct
21 Correct 6 ms 860 KB Output is correct
22 Correct 6 ms 860 KB Output is correct
23 Correct 6 ms 860 KB Output is correct
24 Correct 6 ms 860 KB Output is correct
25 Correct 6 ms 940 KB Output is correct
26 Correct 5 ms 860 KB Output is correct
27 Correct 7 ms 1340 KB Output is correct
28 Correct 6 ms 860 KB Output is correct
29 Correct 5 ms 856 KB Output is correct
30 Correct 6 ms 856 KB Output is correct
31 Correct 7 ms 940 KB Output is correct
32 Correct 7 ms 952 KB Output is correct
33 Correct 8 ms 1116 KB Output is correct
34 Correct 6 ms 964 KB Output is correct
35 Correct 6 ms 1116 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 8 ms 872 KB Output is correct
3 Correct 7 ms 860 KB Output is correct
4 Correct 7 ms 860 KB Output is correct
5 Correct 572 ms 34816 KB Output is correct
6 Correct 625 ms 28680 KB Output is correct
7 Correct 608 ms 33028 KB Output is correct
8 Correct 453 ms 31636 KB Output is correct
9 Correct 499 ms 30604 KB Output is correct
10 Correct 844 ms 37864 KB Output is correct
11 Correct 835 ms 38832 KB Output is correct
12 Correct 808 ms 38032 KB Output is correct
13 Correct 779 ms 38020 KB Output is correct
14 Correct 881 ms 38024 KB Output is correct
15 Correct 844 ms 41652 KB Output is correct
16 Correct 864 ms 41332 KB Output is correct
17 Correct 911 ms 40964 KB Output is correct
18 Correct 831 ms 38240 KB Output is correct
19 Correct 836 ms 38268 KB Output is correct
20 Correct 856 ms 38544 KB Output is correct
21 Correct 673 ms 37832 KB Output is correct
22 Correct 780 ms 38028 KB Output is correct
23 Correct 714 ms 37608 KB Output is correct
24 Correct 733 ms 37816 KB Output is correct
25 Correct 622 ms 38580 KB Output is correct
26 Correct 617 ms 38312 KB Output is correct
27 Correct 651 ms 38916 KB Output is correct
28 Correct 578 ms 38076 KB Output is correct
29 Correct 530 ms 38252 KB Output is correct
30 Correct 589 ms 38072 KB Output is correct
31 Correct 634 ms 38060 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 7 ms 1072 KB Output is correct
3 Correct 6 ms 984 KB Output is correct
4 Correct 7 ms 1268 KB Output is correct
5 Correct 473 ms 36392 KB Output is correct
6 Correct 460 ms 35968 KB Output is correct
7 Correct 578 ms 26736 KB Output is correct
8 Correct 809 ms 41948 KB Output is correct
9 Correct 849 ms 41344 KB Output is correct
10 Correct 895 ms 41380 KB Output is correct
11 Correct 674 ms 41368 KB Output is correct
12 Correct 682 ms 41396 KB Output is correct
13 Correct 692 ms 41400 KB Output is correct
14 Correct 621 ms 41304 KB Output is correct
15 Correct 582 ms 41224 KB Output is correct
16 Correct 659 ms 41368 KB Output is correct
17 Correct 646 ms 41440 KB Output is correct

Subtask #4
32.0 / 32.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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 968 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 7 ms 1104 KB Output is correct
9 Correct 7 ms 1112 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 7 ms 1104 KB Output is correct
12 Correct 7 ms 1064 KB Output is correct
13 Correct 7 ms 980 KB Output is correct
14 Correct 7 ms 1116 KB Output is correct
15 Correct 7 ms 1064 KB Output is correct
16 Correct 7 ms 1024 KB Output is correct
17 Correct 7 ms 1116 KB Output is correct
18 Correct 7 ms 1116 KB Output is correct
19 Correct 7 ms 860 KB Output is correct
20 Correct 6 ms 860 KB Output is correct
21 Correct 6 ms 860 KB Output is correct
22 Correct 6 ms 860 KB Output is correct
23 Correct 6 ms 860 KB Output is correct
24 Correct 6 ms 860 KB Output is correct
25 Correct 6 ms 940 KB Output is correct
26 Correct 5 ms 860 KB Output is correct
27 Correct 7 ms 1340 KB Output is correct
28 Correct 6 ms 860 KB Output is correct
29 Correct 5 ms 856 KB Output is correct
30 Correct 6 ms 856 KB Output is correct
31 Correct 7 ms 940 KB Output is correct
32 Correct 7 ms 952 KB Output is correct
33 Correct 8 ms 1116 KB Output is correct
34 Correct 6 ms 964 KB Output is correct
35 Correct 6 ms 1116 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 8 ms 872 KB Output is correct
38 Correct 7 ms 860 KB Output is correct
39 Correct 7 ms 860 KB Output is correct
40 Correct 572 ms 34816 KB Output is correct
41 Correct 625 ms 28680 KB Output is correct
42 Correct 608 ms 33028 KB Output is correct
43 Correct 453 ms 31636 KB Output is correct
44 Correct 499 ms 30604 KB Output is correct
45 Correct 844 ms 37864 KB Output is correct
46 Correct 835 ms 38832 KB Output is correct
47 Correct 808 ms 38032 KB Output is correct
48 Correct 779 ms 38020 KB Output is correct
49 Correct 881 ms 38024 KB Output is correct
50 Correct 844 ms 41652 KB Output is correct
51 Correct 864 ms 41332 KB Output is correct
52 Correct 911 ms 40964 KB Output is correct
53 Correct 831 ms 38240 KB Output is correct
54 Correct 836 ms 38268 KB Output is correct
55 Correct 856 ms 38544 KB Output is correct
56 Correct 673 ms 37832 KB Output is correct
57 Correct 780 ms 38028 KB Output is correct
58 Correct 714 ms 37608 KB Output is correct
59 Correct 733 ms 37816 KB Output is correct
60 Correct 622 ms 38580 KB Output is correct
61 Correct 617 ms 38312 KB Output is correct
62 Correct 651 ms 38916 KB Output is correct
63 Correct 578 ms 38076 KB Output is correct
64 Correct 530 ms 38252 KB Output is correct
65 Correct 589 ms 38072 KB Output is correct
66 Correct 634 ms 38060 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 7 ms 1072 KB Output is correct
69 Correct 6 ms 984 KB Output is correct
70 Correct 7 ms 1268 KB Output is correct
71 Correct 473 ms 36392 KB Output is correct
72 Correct 460 ms 35968 KB Output is correct
73 Correct 578 ms 26736 KB Output is correct
74 Correct 809 ms 41948 KB Output is correct
75 Correct 849 ms 41344 KB Output is correct
76 Correct 895 ms 41380 KB Output is correct
77 Correct 674 ms 41368 KB Output is correct
78 Correct 682 ms 41396 KB Output is correct
79 Correct 692 ms 41400 KB Output is correct
80 Correct 621 ms 41304 KB Output is correct
81 Correct 582 ms 41224 KB Output is correct
82 Correct 659 ms 41368 KB Output is correct
83 Correct 646 ms 41440 KB Output is correct
84 Correct 536 ms 30624 KB Output is correct
85 Correct 515 ms 24572 KB Output is correct
86 Correct 513 ms 22888 KB Output is correct
87 Correct 850 ms 38572 KB Output is correct
88 Correct 862 ms 38124 KB Output is correct
89 Correct 897 ms 37960 KB Output is correct
90 Correct 774 ms 37968 KB Output is correct
91 Correct 826 ms 38384 KB Output is correct
92 Correct 918 ms 40336 KB Output is correct
93 Correct 886 ms 41016 KB Output is correct
94 Correct 919 ms 38476 KB Output is correct
95 Correct 823 ms 38284 KB Output is correct
96 Correct 828 ms 38268 KB Output is correct
97 Correct 905 ms 38672 KB Output is correct
98 Correct 671 ms 37808 KB Output is correct
99 Correct 787 ms 37488 KB Output is correct
100 Correct 741 ms 37576 KB Output is correct
101 Correct 686 ms 38200 KB Output is correct
102 Correct 629 ms 38804 KB Output is correct
103 Correct 604 ms 38328 KB Output is correct
104 Correct 646 ms 38920 KB Output is correct
105 Correct 650 ms 38612 KB Output is correct
106 Correct 566 ms 38032 KB Output is correct
107 Correct 611 ms 38248 KB Output is correct
108 Correct 608 ms 38044 KB Output is correct