제출 #885906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885906		abysmal	Two Currencies (JOI23_currencies)	C++14	100 / 100	919 ms	41948 KiB

currencies

#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 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32