oj.uz

Submission #856698

# Submission time Handle Problem Language Result Execution time Memory
856698 2023-10-04T10:45:33 Z bkhanh Two Currencies (JOI23_currencies) C++14
0 / 100
 7 ms 24564 KB 
#include<bits/stdc++.h>
using namespace std;    

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

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

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

    struct Query
    {
        long long 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;
    int vis[2000001];
    vector<int> list[M];
    int timeIn[M], timeOut[M];
    vector<long long> valRag;
    int timeDFS;

    long long Sum[2000001];
    long long node[2000001];
    int pos[M];

    vector<Node> adj[M];

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

        for(auto info: adj[u])
        {
            if(info.nxt != par)
            {
                for(auto c: list[info.id]) valRag.push_back(c);
                DFS(info.nxt, u);
                for(auto c: list[info.id]) valRag.push_back(c);
            }
        }

        timeOut[u] = timeDFS;
    }

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

        while(pos)
        {
            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, (-1LL) * get<0>(idVal[id]));
        }

        vis[id] ^= 1;
    }

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

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

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

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

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

            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 < idVal.size(); i++)
        {
            auto t = idVal[i];
            list[get<1>(t)][get<2>(t)] = i;
        }

        DFS(1, 1);

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

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

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

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

        memset(ans, -1, sizeof ans);
        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 = 1; i <= q; i++) cout << ans[i] << '\n';
    }
}

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

    Solve::solve();
}

Compilation message

currencies.cpp: In function 'void Solve::solve()':
currencies.cpp:124:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(int i = 1; i < idVal.size(); i++)
      |                        ~~^~~~~~~~~~~~~~
currencies.cpp:132:13: warning: unused variable 'srt' [-Wunused-variable]
  132 |         int srt = sqrt(valRag.size());
      |             ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24152 KB Output is correct
2 Correct 4 ms 24408 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 4 ms 24156 KB Output is correct
5 Incorrect 5 ms 18268 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24156 KB Output is correct
2 Incorrect 5 ms 18520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18012 KB Output is correct
2 Incorrect 7 ms 24564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24152 KB Output is correct
2 Correct 4 ms 24408 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 4 ms 24156 KB Output is correct
5 Incorrect 5 ms 18268 KB Output isn't correct
6 Halted 0 ms 0 KB -