Submission #856747

#	Time	Username	Problem	Language	Result	Execution time	Memory
856747		bkhanh	Two Currencies (JOI23_currencies)	C++14	100 / 100	3353 ms	58276 KiB

currencies

#include<bits/stdc++.h>
using namespace std;    

namespace Solve
{
    #define int long long
    const int M = 2e5 + 1;
    const int Srt = 400;

    typedef tuple<int, int, int> ox;
    vector<ox> idVal;

    int ans[M];
    
    struct Node
    {
        int nxt, id;
    };

    struct Query
    {
        int Comp, id, x, y, z, w;

        bool operator < (const Query that)
        {
            if(Comp != that.Comp) return Comp < that.Comp;
            if(y != that.y) return y < that.y;
            return x < that.x;
        }
    };

    vector<Query> List;
    bool vis[2000001];
    vector<int> list[M];
    int timeIn[M], timeOut[M];
    vector<int> valRag;
    int timeDFS;

    int Sum[4000001];
    int node[4000001];
    int pos[M];

    vector<Node> adj[M];

    void DFS(int u, int par)
    {
        pos[u] = valRag.size();

        for(auto info: adj[u])
        {
            if(info.nxt == par) continue;

                for(auto c: list[info.id]) valRag.push_back(c);
                DFS(info.nxt, u);
                for(auto c: list[info.id]) valRag.push_back(c);
        }
    }

    void Update(int pos, int val)
    {
        pos += (1 << 19);

        while(pos != 0)
        {
            Sum[pos] += val;
            node[pos] += (val > 0) ? 1 : -1;
            pos /= 2;
        }
    }

    void Up(int id)
    {
        if(!vis[id])
        {
            Update(id, get<0>(idVal[id]));
        }
        else
        {
            Update(id, -get<0>(idVal[id]));
        }

        vis[id] = !vis[id];
    }

    int cal(int id, int val)
    {
        if(id >= (1 << 19))
        {
            return 0;
        }

        if(Sum[id * 2] <= val) return cal(id * 2 + 1, val - Sum[2 * id]) + node[2 * id];
        
        return cal(id * 2, val);
    }

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

        for(int i = 0; i < n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        for(int i = 1; i <= m; i++)
        {
            int id, c;
            cin >> id >> c;
            id--;

            idVal.push_back({c, id, list[id].size()});
            list[id].push_back(c);
        }

        idVal.push_back({0, -1, -1});
        sort(idVal.begin(), idVal.end());

        for(int i = 1; i < (int)idVal.size(); i++)
        {
            auto t = idVal[i];
            list[get<1>(t)][get<2>(t)] = i;
        }

        DFS(0, -1);

        int Sr = sqrt(valRag.size());
        for(int i = 0; i < q; i++)
        {
            int x, y, z, w;
            cin >> x >> y >> z >> w;
            x--;
            y--;

            x = pos[x];
            y = pos[y];

            if(x > y) swap(x, y);

            List.push_back({x / Sr, i, x, y, z, w});
        }

        sort(List.begin(), List.end());

        int l = 0, r = 0;

        for(auto info: List)
        {
            while(l < info.x)
            {
                Up(valRag[l]);
                l++;
            }

            while(info.x < l)
            {
                l--;
                Up(valRag[l]);
            }

            while(r < info.y)
            {
                Up(valRag[r]);
                r++;
            }

            while(info.y < r)
            {
                r--;
                Up(valRag[r]);
            }

            int Val = cal(1, info.w);

            if(node[1] > info.z + Val)
            {
                ans[info.id] = -1;
            }
            else
            {
                ans[info.id] = info.z + Val - node[1];
            }
        }

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

main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve::solve();
}

Compilation message (stderr)

currencies.cpp:196:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  196 | main()
      | ^~~~

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