oj.uz

Submission #856747

# Submission time Handle Problem Language Result Execution time Memory
856747 2023-10-04T12:25:41 Z bkhanh Two Currencies (JOI23_currencies) C++14
100 / 100
 3353 ms 58276 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 4 ms 27296 KB Output is correct
5 Correct 11 ms 27480 KB Output is correct
6 Correct 13 ms 27740 KB Output is correct
7 Correct 10 ms 27484 KB Output is correct
8 Correct 13 ms 27584 KB Output is correct
9 Correct 13 ms 27740 KB Output is correct
10 Correct 13 ms 27744 KB Output is correct
11 Correct 13 ms 27740 KB Output is correct
12 Correct 13 ms 27584 KB Output is correct
13 Correct 9 ms 27740 KB Output is correct
14 Correct 9 ms 27880 KB Output is correct
15 Correct 10 ms 27740 KB Output is correct
16 Correct 11 ms 27768 KB Output is correct
17 Correct 11 ms 27740 KB Output is correct
18 Correct 11 ms 27740 KB Output is correct
19 Correct 12 ms 27740 KB Output is correct
20 Correct 13 ms 27740 KB Output is correct
21 Correct 13 ms 27740 KB Output is correct
22 Correct 13 ms 27588 KB Output is correct
23 Correct 7 ms 27612 KB Output is correct
24 Correct 9 ms 27740 KB Output is correct
25 Correct 8 ms 27736 KB Output is correct
26 Correct 6 ms 27740 KB Output is correct
27 Correct 6 ms 27504 KB Output is correct
28 Correct 9 ms 27740 KB Output is correct
29 Correct 10 ms 27736 KB Output is correct
30 Correct 13 ms 27740 KB Output is correct
31 Correct 12 ms 27740 KB Output is correct
32 Correct 14 ms 27992 KB Output is correct
33 Correct 9 ms 27736 KB Output is correct
34 Correct 8 ms 27740 KB Output is correct
35 Correct 9 ms 27740 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 KB Output is correct
2 Correct 13 ms 27736 KB Output is correct
3 Correct 13 ms 27740 KB Output is correct
4 Correct 13 ms 27936 KB Output is correct
5 Correct 2275 ms 43216 KB Output is correct
6 Correct 2066 ms 44896 KB Output is correct
7 Correct 1641 ms 43108 KB Output is correct
8 Correct 1428 ms 43248 KB Output is correct
9 Correct 1562 ms 42692 KB Output is correct
10 Correct 2803 ms 46092 KB Output is correct
11 Correct 2766 ms 47324 KB Output is correct
12 Correct 2857 ms 46616 KB Output is correct
13 Correct 2788 ms 45628 KB Output is correct
14 Correct 2909 ms 45624 KB Output is correct
15 Correct 2086 ms 55432 KB Output is correct
16 Correct 2198 ms 56620 KB Output is correct
17 Correct 1126 ms 55264 KB Output is correct
18 Correct 2775 ms 45880 KB Output is correct
19 Correct 2632 ms 45600 KB Output is correct
20 Correct 2596 ms 46268 KB Output is correct
21 Correct 2468 ms 44924 KB Output is correct
22 Correct 2403 ms 44956 KB Output is correct
23 Correct 2445 ms 46236 KB Output is correct
24 Correct 2413 ms 45612 KB Output is correct
25 Correct 460 ms 45164 KB Output is correct
26 Correct 382 ms 46964 KB Output is correct
27 Correct 196 ms 47400 KB Output is correct
28 Correct 112 ms 45736 KB Output is correct
29 Correct 126 ms 45496 KB Output is correct
30 Correct 2279 ms 47352 KB Output is correct
31 Correct 2294 ms 45628 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 9 ms 27740 KB Output is correct
3 Correct 9 ms 27960 KB Output is correct
4 Correct 8 ms 27740 KB Output is correct
5 Correct 612 ms 52104 KB Output is correct
6 Correct 486 ms 51428 KB Output is correct
7 Correct 1047 ms 49884 KB Output is correct
8 Correct 1175 ms 56496 KB Output is correct
9 Correct 1155 ms 58276 KB Output is correct
10 Correct 1124 ms 56752 KB Output is correct
11 Correct 309 ms 55920 KB Output is correct
12 Correct 365 ms 55752 KB Output is correct
13 Correct 332 ms 56388 KB Output is correct
14 Correct 112 ms 57456 KB Output is correct
15 Correct 118 ms 56440 KB Output is correct
16 Correct 768 ms 56840 KB Output is correct
17 Correct 801 ms 58228 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 4 ms 27296 KB Output is correct
5 Correct 11 ms 27480 KB Output is correct
6 Correct 13 ms 27740 KB Output is correct
7 Correct 10 ms 27484 KB Output is correct
8 Correct 13 ms 27584 KB Output is correct
9 Correct 13 ms 27740 KB Output is correct
10 Correct 13 ms 27744 KB Output is correct
11 Correct 13 ms 27740 KB Output is correct
12 Correct 13 ms 27584 KB Output is correct
13 Correct 9 ms 27740 KB Output is correct
14 Correct 9 ms 27880 KB Output is correct
15 Correct 10 ms 27740 KB Output is correct
16 Correct 11 ms 27768 KB Output is correct
17 Correct 11 ms 27740 KB Output is correct
18 Correct 11 ms 27740 KB Output is correct
19 Correct 12 ms 27740 KB Output is correct
20 Correct 13 ms 27740 KB Output is correct
21 Correct 13 ms 27740 KB Output is correct
22 Correct 13 ms 27588 KB Output is correct
23 Correct 7 ms 27612 KB Output is correct
24 Correct 9 ms 27740 KB Output is correct
25 Correct 8 ms 27736 KB Output is correct
26 Correct 6 ms 27740 KB Output is correct
27 Correct 6 ms 27504 KB Output is correct
28 Correct 9 ms 27740 KB Output is correct
29 Correct 10 ms 27736 KB Output is correct
30 Correct 13 ms 27740 KB Output is correct
31 Correct 12 ms 27740 KB Output is correct
32 Correct 14 ms 27992 KB Output is correct
33 Correct 9 ms 27736 KB Output is correct
34 Correct 8 ms 27740 KB Output is correct
35 Correct 9 ms 27740 KB Output is correct
36 Correct 4 ms 27224 KB Output is correct
37 Correct 13 ms 27736 KB Output is correct
38 Correct 13 ms 27740 KB Output is correct
39 Correct 13 ms 27936 KB Output is correct
40 Correct 2275 ms 43216 KB Output is correct
41 Correct 2066 ms 44896 KB Output is correct
42 Correct 1641 ms 43108 KB Output is correct
43 Correct 1428 ms 43248 KB Output is correct
44 Correct 1562 ms 42692 KB Output is correct
45 Correct 2803 ms 46092 KB Output is correct
46 Correct 2766 ms 47324 KB Output is correct
47 Correct 2857 ms 46616 KB Output is correct
48 Correct 2788 ms 45628 KB Output is correct
49 Correct 2909 ms 45624 KB Output is correct
50 Correct 2086 ms 55432 KB Output is correct
51 Correct 2198 ms 56620 KB Output is correct
52 Correct 1126 ms 55264 KB Output is correct
53 Correct 2775 ms 45880 KB Output is correct
54 Correct 2632 ms 45600 KB Output is correct
55 Correct 2596 ms 46268 KB Output is correct
56 Correct 2468 ms 44924 KB Output is correct
57 Correct 2403 ms 44956 KB Output is correct
58 Correct 2445 ms 46236 KB Output is correct
59 Correct 2413 ms 45612 KB Output is correct
60 Correct 460 ms 45164 KB Output is correct
61 Correct 382 ms 46964 KB Output is correct
62 Correct 196 ms 47400 KB Output is correct
63 Correct 112 ms 45736 KB Output is correct
64 Correct 126 ms 45496 KB Output is correct
65 Correct 2279 ms 47352 KB Output is correct
66 Correct 2294 ms 45628 KB Output is correct
67 Correct 3 ms 16984 KB Output is correct
68 Correct 9 ms 27740 KB Output is correct
69 Correct 9 ms 27960 KB Output is correct
70 Correct 8 ms 27740 KB Output is correct
71 Correct 612 ms 52104 KB Output is correct
72 Correct 486 ms 51428 KB Output is correct
73 Correct 1047 ms 49884 KB Output is correct
74 Correct 1175 ms 56496 KB Output is correct
75 Correct 1155 ms 58276 KB Output is correct
76 Correct 1124 ms 56752 KB Output is correct
77 Correct 309 ms 55920 KB Output is correct
78 Correct 365 ms 55752 KB Output is correct
79 Correct 332 ms 56388 KB Output is correct
80 Correct 112 ms 57456 KB Output is correct
81 Correct 118 ms 56440 KB Output is correct
82 Correct 768 ms 56840 KB Output is correct
83 Correct 801 ms 58228 KB Output is correct
84 Correct 2508 ms 43340 KB Output is correct
85 Correct 2234 ms 42964 KB Output is correct
86 Correct 1375 ms 40864 KB Output is correct
87 Correct 2981 ms 46664 KB Output is correct
88 Correct 3080 ms 46076 KB Output is correct
89 Correct 2982 ms 46256 KB Output is correct
90 Correct 3091 ms 47032 KB Output is correct
91 Correct 3002 ms 46348 KB Output is correct
92 Correct 1436 ms 52412 KB Output is correct
93 Correct 1316 ms 55860 KB Output is correct
94 Correct 3353 ms 45852 KB Output is correct
95 Correct 3103 ms 45696 KB Output is correct
96 Correct 2859 ms 45880 KB Output is correct
97 Correct 3081 ms 47336 KB Output is correct
98 Correct 2856 ms 44928 KB Output is correct
99 Correct 2932 ms 46780 KB Output is correct
100 Correct 3183 ms 46168 KB Output is correct
101 Correct 2911 ms 44948 KB Output is correct
102 Correct 231 ms 45164 KB Output is correct
103 Correct 260 ms 45168 KB Output is correct
104 Correct 674 ms 45864 KB Output is correct
105 Correct 111 ms 45560 KB Output is correct
106 Correct 111 ms 46240 KB Output is correct
107 Correct 2803 ms 45872 KB Output is correct
108 Correct 3067 ms 45960 KB Output is correct