oj.uz

Submission #856756

# Submission time Handle Problem Language Result Execution time Memory
856756 2023-10-04T12:55:44 Z bkhanh Two Currencies (JOI23_currencies) C++14
100 / 100
 2072 ms 41808 KB 
#include<bits/stdc++.h>
using namespace std;    

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

    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;
    bool vis[2000001];
    vector<int> list[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)
    {
        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);
            }
        }
    }

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

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

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

        vis[id] ^= 1;
    }

    long long cal(int id, long long val)
    {
        if(id >= (1 << 17))
        {
            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);

        for(int i = 1; i <= q; i++)
        {
            long long 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]);
            }

            long long 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';
    }
}

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:120: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]
  120 |         for(int i = 1; i < idVal.size(); i++)
      |                        ~~^~~~~~~~~~~~~~
currencies.cpp: At global scope:
currencies.cpp:189:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  189 | main()
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14752 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 14756 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 10 ms 15196 KB Output is correct
7 Correct 10 ms 15148 KB Output is correct
8 Correct 11 ms 15196 KB Output is correct
9 Correct 12 ms 15376 KB Output is correct
10 Correct 11 ms 15196 KB Output is correct
11 Correct 11 ms 15292 KB Output is correct
12 Correct 11 ms 15196 KB Output is correct
13 Correct 10 ms 15528 KB Output is correct
14 Correct 9 ms 15480 KB Output is correct
15 Correct 13 ms 15196 KB Output is correct
16 Correct 11 ms 15196 KB Output is correct
17 Correct 11 ms 15196 KB Output is correct
18 Correct 10 ms 15420 KB Output is correct
19 Correct 10 ms 15196 KB Output is correct
20 Correct 11 ms 15388 KB Output is correct
21 Correct 11 ms 15320 KB Output is correct
22 Correct 10 ms 15196 KB Output is correct
23 Correct 6 ms 15196 KB Output is correct
24 Correct 4 ms 15196 KB Output is correct
25 Correct 6 ms 15708 KB Output is correct
26 Correct 4 ms 15344 KB Output is correct
27 Correct 4 ms 15196 KB Output is correct
28 Correct 6 ms 15196 KB Output is correct
29 Correct 5 ms 15196 KB Output is correct
30 Correct 11 ms 15196 KB Output is correct
31 Correct 11 ms 15196 KB Output is correct
32 Correct 11 ms 15196 KB Output is correct
33 Correct 9 ms 15452 KB Output is correct
34 Correct 9 ms 15544 KB Output is correct
35 Correct 10 ms 15452 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 11 ms 15192 KB Output is correct
3 Correct 11 ms 15192 KB Output is correct
4 Correct 15 ms 15372 KB Output is correct
5 Correct 1380 ms 29752 KB Output is correct
6 Correct 1329 ms 31688 KB Output is correct
7 Correct 1014 ms 28652 KB Output is correct
8 Correct 890 ms 26052 KB Output is correct
9 Correct 921 ms 28280 KB Output is correct
10 Correct 1848 ms 33772 KB Output is correct
11 Correct 1807 ms 31748 KB Output is correct
12 Correct 1808 ms 32452 KB Output is correct
13 Correct 1889 ms 32856 KB Output is correct
14 Correct 1971 ms 31752 KB Output is correct
15 Correct 1477 ms 40328 KB Output is correct
16 Correct 1497 ms 41196 KB Output is correct
17 Correct 860 ms 41048 KB Output is correct
18 Correct 1777 ms 31376 KB Output is correct
19 Correct 1704 ms 32952 KB Output is correct
20 Correct 1694 ms 32268 KB Output is correct
21 Correct 1372 ms 29900 KB Output is correct
22 Correct 1371 ms 31680 KB Output is correct
23 Correct 1379 ms 32352 KB Output is correct
24 Correct 1463 ms 33888 KB Output is correct
25 Correct 301 ms 32632 KB Output is correct
26 Correct 235 ms 31348 KB Output is correct
27 Correct 148 ms 31344 KB Output is correct
28 Correct 110 ms 31832 KB Output is correct
29 Correct 110 ms 31860 KB Output is correct
30 Correct 1417 ms 33232 KB Output is correct
31 Correct 1397 ms 32468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 9 ms 15452 KB Output is correct
3 Correct 10 ms 15552 KB Output is correct
4 Correct 9 ms 15452 KB Output is correct
5 Correct 543 ms 34368 KB Output is correct
6 Correct 445 ms 35192 KB Output is correct
7 Correct 835 ms 35924 KB Output is correct
8 Correct 928 ms 41008 KB Output is correct
9 Correct 936 ms 41580 KB Output is correct
10 Correct 1048 ms 40816 KB Output is correct
11 Correct 230 ms 41280 KB Output is correct
12 Correct 261 ms 41648 KB Output is correct
13 Correct 292 ms 40664 KB Output is correct
14 Correct 111 ms 41588 KB Output is correct
15 Correct 122 ms 41144 KB Output is correct
16 Correct 553 ms 41808 KB Output is correct
17 Correct 555 ms 40564 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14752 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 14756 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 10 ms 15196 KB Output is correct
7 Correct 10 ms 15148 KB Output is correct
8 Correct 11 ms 15196 KB Output is correct
9 Correct 12 ms 15376 KB Output is correct
10 Correct 11 ms 15196 KB Output is correct
11 Correct 11 ms 15292 KB Output is correct
12 Correct 11 ms 15196 KB Output is correct
13 Correct 10 ms 15528 KB Output is correct
14 Correct 9 ms 15480 KB Output is correct
15 Correct 13 ms 15196 KB Output is correct
16 Correct 11 ms 15196 KB Output is correct
17 Correct 11 ms 15196 KB Output is correct
18 Correct 10 ms 15420 KB Output is correct
19 Correct 10 ms 15196 KB Output is correct
20 Correct 11 ms 15388 KB Output is correct
21 Correct 11 ms 15320 KB Output is correct
22 Correct 10 ms 15196 KB Output is correct
23 Correct 6 ms 15196 KB Output is correct
24 Correct 4 ms 15196 KB Output is correct
25 Correct 6 ms 15708 KB Output is correct
26 Correct 4 ms 15344 KB Output is correct
27 Correct 4 ms 15196 KB Output is correct
28 Correct 6 ms 15196 KB Output is correct
29 Correct 5 ms 15196 KB Output is correct
30 Correct 11 ms 15196 KB Output is correct
31 Correct 11 ms 15196 KB Output is correct
32 Correct 11 ms 15196 KB Output is correct
33 Correct 9 ms 15452 KB Output is correct
34 Correct 9 ms 15544 KB Output is correct
35 Correct 10 ms 15452 KB Output is correct
36 Correct 2 ms 14940 KB Output is correct
37 Correct 11 ms 15192 KB Output is correct
38 Correct 11 ms 15192 KB Output is correct
39 Correct 15 ms 15372 KB Output is correct
40 Correct 1380 ms 29752 KB Output is correct
41 Correct 1329 ms 31688 KB Output is correct
42 Correct 1014 ms 28652 KB Output is correct
43 Correct 890 ms 26052 KB Output is correct
44 Correct 921 ms 28280 KB Output is correct
45 Correct 1848 ms 33772 KB Output is correct
46 Correct 1807 ms 31748 KB Output is correct
47 Correct 1808 ms 32452 KB Output is correct
48 Correct 1889 ms 32856 KB Output is correct
49 Correct 1971 ms 31752 KB Output is correct
50 Correct 1477 ms 40328 KB Output is correct
51 Correct 1497 ms 41196 KB Output is correct
52 Correct 860 ms 41048 KB Output is correct
53 Correct 1777 ms 31376 KB Output is correct
54 Correct 1704 ms 32952 KB Output is correct
55 Correct 1694 ms 32268 KB Output is correct
56 Correct 1372 ms 29900 KB Output is correct
57 Correct 1371 ms 31680 KB Output is correct
58 Correct 1379 ms 32352 KB Output is correct
59 Correct 1463 ms 33888 KB Output is correct
60 Correct 301 ms 32632 KB Output is correct
61 Correct 235 ms 31348 KB Output is correct
62 Correct 148 ms 31344 KB Output is correct
63 Correct 110 ms 31832 KB Output is correct
64 Correct 110 ms 31860 KB Output is correct
65 Correct 1417 ms 33232 KB Output is correct
66 Correct 1397 ms 32468 KB Output is correct
67 Correct 2 ms 10844 KB Output is correct
68 Correct 9 ms 15452 KB Output is correct
69 Correct 10 ms 15552 KB Output is correct
70 Correct 9 ms 15452 KB Output is correct
71 Correct 543 ms 34368 KB Output is correct
72 Correct 445 ms 35192 KB Output is correct
73 Correct 835 ms 35924 KB Output is correct
74 Correct 928 ms 41008 KB Output is correct
75 Correct 936 ms 41580 KB Output is correct
76 Correct 1048 ms 40816 KB Output is correct
77 Correct 230 ms 41280 KB Output is correct
78 Correct 261 ms 41648 KB Output is correct
79 Correct 292 ms 40664 KB Output is correct
80 Correct 111 ms 41588 KB Output is correct
81 Correct 122 ms 41144 KB Output is correct
82 Correct 553 ms 41808 KB Output is correct
83 Correct 555 ms 40564 KB Output is correct
84 Correct 1649 ms 28928 KB Output is correct
85 Correct 1398 ms 29848 KB Output is correct
86 Correct 923 ms 24468 KB Output is correct
87 Correct 2072 ms 32752 KB Output is correct
88 Correct 1976 ms 31752 KB Output is correct
89 Correct 2037 ms 33904 KB Output is correct
90 Correct 1950 ms 33668 KB Output is correct
91 Correct 1951 ms 33156 KB Output is correct
92 Correct 1107 ms 36968 KB Output is correct
93 Correct 986 ms 41272 KB Output is correct
94 Correct 2048 ms 32892 KB Output is correct
95 Correct 1993 ms 32016 KB Output is correct
96 Correct 1936 ms 31864 KB Output is correct
97 Correct 1941 ms 31356 KB Output is correct
98 Correct 1857 ms 33108 KB Output is correct
99 Correct 1813 ms 32256 KB Output is correct
100 Correct 1788 ms 32300 KB Output is correct
101 Correct 1890 ms 31924 KB Output is correct
102 Correct 187 ms 31340 KB Output is correct
103 Correct 206 ms 31208 KB Output is correct
104 Correct 474 ms 31940 KB Output is correct
105 Correct 120 ms 32348 KB Output is correct
106 Correct 113 ms 31608 KB Output is correct
107 Correct 1467 ms 32884 KB Output is correct
108 Correct 1501 ms 32288 KB Output is correct