Submission #955440

#	Time	Username	Problem	Language	Result	Execution time	Memory
955440		Requiem	Two Currencies (JOI23_currencies)	C++17	100 / 100	1848 ms	156536 KiB

currencies

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "k"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 5e5 + 9;


struct Station{
    int pos_edge;
    int fee_silver;
    Station(int pos_edge = 0, int fee_silver = 0):
        pos_edge(pos_edge), fee_silver(fee_silver){}
};
struct Query{
    int start, destination, silver, gold;
    Query(int start = 0, int destination = 0, int silver = 0, int gold = 0):
        start(start), destination(destination), silver(silver), gold(gold){}
};

int n, m, q;
vector<int> g[MAXN];     ii edge[MAXN];
vector<pair<int, Query>> SetQuery;
vector<Station> SetStation;
map<int, vector<int>> mp;

namespace sub1{
    int par[MAXN], depth[MAXN];
    void dfs(int u,int p){

        for(auto e: g[u]){
            int v = edge[e].fi + edge[e].se - u;
            if (v == p) continue;
            par[v] = e;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    int getpath(int u,int v,int gold,int silver){
         vector<int> path;
         int sum = 0;
         while(u != v){
//                cerr << u << ' ' << v << endl;
                if (depth[u] < depth[v]) swap(u, v);
                int edge_to_p = par[u];
                if (mp[edge_to_p].size() != 0){
                    for(auto v: mp[edge_to_p]){
                        path.pb(v);
                        sum += v;
                    }
                }
                u = edge[edge_to_p].fi + edge[edge_to_p].se - u;
         }
         sum = 0;
         for(auto x: path){
             sum += x;
         }
         sort(path.begin(), path.end());
         int cnt = 0;
         while(sum > silver and path.size() > 0){
               cnt++;
               sum -= path.back();
               path.pop_back();
         }
         return max(gold - cnt, -1LL);
    }
    void solve(){
        dfs(1, -1);
//        for(int i = 1; i <= n; i++){
//            cout << depth[i] << ' ' << par[i] << endl;
//        }
        for(int i = 0; i < q; i++){
            int u = SetQuery[i].se.start;
            int v = SetQuery[i].se.destination;
            int golden = SetQuery[i].se.gold;
            int silver = SetQuery[i].se.silver;
            cout << getpath(u, v, golden, silver) << endl;

        }

    }
}

struct segtree{
    vector<int> BIT;
    int sz;
    void init(int _sz){
         sz = _sz;
         BIT.resize(sz + 9);
    }
    void reset(){
         fill(BIT.begin(), BIT.end(), 0);
    }

    void update(int pos,int x){
         pos++;
         for(int i = pos; i <= sz; i += i & (-i)){
             BIT[i] += x;
//             cout << "UPD: " << i << ' ' << x << endl;
         }
    }
    int get(int pos){
         int res = 0;
//         cout << u << ' ' << BIT[u] << endl;
         for(int i = pos; i > 0; i -= i & (-i)){
             res += BIT[i];
         }
         return res;
    }
    int getsum(int u,int v){
        u++; v++;

        return get(v) - get(u - 1);
    }

};
namespace sub4{

    int sz[MAXN], depth[MAXN], par[MAXN];
    void precalc(int u,int p){
        sz[u] = 1;
        for(auto e: g[u]){
            int v = edge[e].fi + edge[e].se - u;
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            par[v] = u;
            precalc(v, u);
            sz[u] += sz[v];
        }
    }

    vector<int> etour;
    int HeadChain[MAXN], IdChain[MAXN], in[MAXN], out[MAXN], PosOnChain[MAXN], NumChain;

    void buildHLD(int u,int p,int curchain){
         PosOnChain[u] = etour.size();
         IdChain[u] = curchain;
         if (etour.size() > 0 and IdChain[etour.back()] != curchain){
             HeadChain[curchain] = u;
         }
         else if (etour.size() == 0) HeadChain[curchain] = u;
         in[u] = etour.size();
         etour.pb(u);

         int bigchild = -1;
         for(auto e: g[u]){
             int v = edge[e].fi + edge[e].se - u;
             if (v == p) continue;
             if (bigchild == -1 or sz[bigchild] < sz[v]){
                 bigchild = v;
             }
         }

         if (bigchild != -1) buildHLD(bigchild, u, curchain);

         for(auto e: g[u]){
             int v = edge[e].fi + edge[e].se - u;
             if (v == p or v== bigchild) continue;
             buildHLD(v, u, ++NumChain);
         }
    }

    vector<int> listvalue;
    unordered_map<int, int> TransferValue;
    int lo[MAXN], hi[MAXN], MinimumWeightQuery[MAXN], NumNode[MAXN], Sum[MAXN], NumStationOn[MAXN], answer[MAXN];
    vector<int> checkQuery[MAXN];

    segtree st_numw, st_sumw;

    ii getsum(int u,int v){
        ii res = {0, 0};  //res.fi: sum
                          //res.se: num
        while(IdChain[u] != IdChain[v]){
            if (depth[HeadChain[IdChain[u]]] < depth[HeadChain[IdChain[v]]]){
                swap(u, v);
            }
//            cout << "LEO: " << u << ' ' < PosOnChain[HeadChain[IdChain[u]]] << ' ' << IdChain;
            res.fi += st_sumw.getsum(PosOnChain[HeadChain[IdChain[u]]], PosOnChain[u]);
            res.se += st_numw.getsum(PosOnChain[HeadChain[IdChain[u]]], PosOnChain[u]);
            u = par[HeadChain[IdChain[u]]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        res.fi += st_sumw.getsum(PosOnChain[u] + 1, PosOnChain[v]);
        res.se += st_numw.getsum(PosOnChain[u] + 1, PosOnChain[v]);
        return res;

    }
    void parallel_binary_search(int n){
        for(int i = 0; i < q; i++){
            lo[i] = 0, hi[i] = listvalue.size() - 1;
        }
//        for(int i = 0; i < n; i++){
//            cout << listvalue[i] << ' ';
//        }
//        cout << endl;
        sort(SetStation.begin(), SetStation.end(), [&](const Station &a, const Station &b){
             return a.fee_silver < b.fee_silver;
        });
        st_sumw.init(n);
        st_numw.init(n);
        while(true){
            st_numw.reset();
            st_sumw.reset();
            bool check = false;
            for(int i = 0; i < listvalue.size(); i++){
                checkQuery[i].clear();
            }
            for(int i = 0; i < q; i++){
                if (lo[i] > hi[i]) {
                    continue;
                }
                int mid = (lo[i] + hi[i]) >> 1;
                checkQuery[mid].pb(i);
                check = true;
//                cout << lo[i] << ' ' << hi[i] << endl;
            }
//            cout << endl;
            if (!check) break;
            int ptr = -1;
            for(int i = 0; i < listvalue.size(); i++){
                while(ptr + 1 < m and SetStation[ptr + 1].fee_silver < listvalue[i]){
                      ptr++;
                      int IdEdge = SetStation[ptr].pos_edge;
                      int u = edge[IdEdge].fi;
                      int v = edge[IdEdge].se;
                      int fee = SetStation[ptr].fee_silver;
                      if (depth[u] < depth[v]) swap(u, v);
//                      cout << i << ' ' << "STATION: " << u << ' ' << fee << endl;

                      st_sumw.update(in[u], fee);
                      st_numw.update(in[u], 1);
                }
//                ii p = getsum(3, 4);
//                cout << p.fi << ' ' << p.se << endl;

                for(auto idQuery: checkQuery[i]){
                    int u = SetQuery[idQuery].se.start;
                    int v = SetQuery[idQuery].se.destination;
                    int silver = SetQuery[idQuery].se.silver;
                    ii sumpath = getsum(u, v);
                    if (sumpath.fi <= silver){
                        lo[idQuery] = i + 1;
                        MinimumWeightQuery[idQuery] = i;
                        Sum[idQuery] = sumpath.fi;
                        NumNode[idQuery] = sumpath.se;
                    }
                    else{
                        hi[idQuery] = i - 1;
                    }
                }
            }
        }
    }

    vector<int> Categorizing[MAXN], Event[MAXN];
    int getval(int x){
        return lower_bound(listvalue.begin(), listvalue.end(), x) - listvalue.begin();
    }
    void getans(){
//        for(int i = 0; i < q; i++){
//            cout << MinimumWeightQuery[i] << ' ' << Sum[i] << ' ' << NumNode[i] << endl;
//        }
        for(int i = 0; i < q; i++){
            Categorizing[MinimumWeightQuery[i]].pb(i);
        }
        for(int i = 0; i < m; i++){
            Event[getval(SetStation[i].fee_silver)].pb(i);
        }
        st_numw.reset();
        for(int i = 0; i < m; i++){
                int idedge = SetStation[i].pos_edge;
                int u = edge[idedge].fi;
                int v = edge[idedge].se;
                if (depth[u] < depth[v]) swap(u, v);
                st_numw.update(in[u], 1);
        }
        for(int i = 0; i < q; i++){
            int u = SetQuery[i].se.start;
            int v = SetQuery[i].se.destination;
            NumStationOn[i] = getsum(u, v).se;
        }
        st_numw.reset();
        for(int i = 0; i < listvalue.size(); i++){
            for(auto idstation: Event[i]){
                int idedge = SetStation[idstation].pos_edge;
                int u = edge[idedge].fi;
                int v = edge[idedge].se;
                if (depth[u] < depth[v]) swap(u, v);
                st_numw.update(in[u], 1);
            }
            for(auto x: Categorizing[i]){
                if (i == listvalue.size() - 1) answer[x] = SetQuery[x].second.gold;
                else{
                    int already_built = Sum[x];
                    int u = SetQuery[x].se.destination;
                    int v = SetQuery[x].se.start;
                    int left = SetQuery[x].second.silver - already_built;
                    int usedgold = NumStationOn[x] - NumNode[x];
                    usedgold -= left / listvalue[i];
                    answer[x] = max(SetQuery[x].se.gold - usedgold, -1LL);
                }
            }
            for(auto idstation: Event[i]){
                int idedge = SetStation[idstation].pos_edge;
                int u = edge[idedge].fi;
                int v = edge[idedge].se;
                if (depth[u] < depth[v]) swap(u, v);
                st_numw.update(in[u], -1);
            }
        }
        for(int i = 0; i < q; i++){
            cout << answer[i] << endl;
        }

    }
    void solve(){
        for(auto station: SetStation){
            listvalue.pb(station.fee_silver);
        }
        listvalue.pb(INF + 1);
        sort(listvalue.begin(), listvalue.end());
        listvalue.erase(unique(listvalue.begin(), listvalue.end()), listvalue.end());

        for(int i = 0; i < listvalue.size(); i++){
            TransferValue[listvalue[i]] = i;
        }

        precalc(1, -1);
        buildHLD(1, -1, ++NumChain);
//        for(int i = 1; i <= n; i++){
//            cout << in[i] << ' ' << par[i] << ' ' << depth[i] << ' ' << i << endl;
//        }
//        for(auto x: etour){
//            cout << x << ' ';
//        }
//        cout << endl;
//        for(int i = 1; i <= NumChain; i++){
//            cout << HeadChain[i] << ' ';
//        }
//        cout << endl;
        parallel_binary_search(n);
        getans();
    }


}
main()
{
    fast;
   if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
   }
   cin >> n >> m >> q;
   for(int i = 1; i < n; i++){
       int u, v;
       cin >> u >> v;
       edge[i] = {u, v};
       g[u].pb(i);
       g[v].pb(i);
   }

   for(int i = 0; i < m; i++){
       int node, fee = 0;
       cin >> node >> fee;
       SetStation.pb(Station(node, fee));
       mp[node].pb(fee);

   }

   for(int i = 0 ; i < q; i++){
       int u, v, silver, gold;
       cin >> u >> v >> gold >> silver;
       SetQuery.pb({i, Query(u, v, silver, gold)});
   }
   sub4::solve();
}

Compilation message (stderr)

currencies.cpp: In function 'void sub4::parallel_binary_search(long long int)':
currencies.cpp:221:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |             for(int i = 0; i < listvalue.size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~~
currencies.cpp:236:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |             for(int i = 0; i < listvalue.size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'void sub4::getans()':
currencies.cpp:299:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  299 |         for(int i = 0; i < listvalue.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~
currencies.cpp:308:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  308 |                 if (i == listvalue.size() - 1) answer[x] = SetQuery[x].second.gold;
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:311:25: warning: unused variable 'u' [-Wunused-variable]
  311 |                     int u = SetQuery[x].se.destination;
      |                         ^
currencies.cpp:312:25: warning: unused variable 'v' [-Wunused-variable]
  312 |                     int v = SetQuery[x].se.start;
      |                         ^
currencies.cpp: In function 'void sub4::solve()':
currencies.cpp:340:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  340 |         for(int i = 0; i < listvalue.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~
currencies.cpp: At global scope:
currencies.cpp:363:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  363 | main()
      | ^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:367:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  367 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:368:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  368 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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