fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
  3. #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
  4. #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
  5. #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
  6. #define ALL(v) (v).begin(),(v).end()
  7. #define fi   first
  8. #define se   second
  9. #define MASK(i) (1LL<<(i))
  10. #define BIT(x,i) (((x)>>(i))&1)
  11. #define div   ___div
  12. #define next   ___next
  13. #define prev   ___prev
  14. #define left   ___left
  15. #define right   ___right
  16. #define __builtin_popcount __builtin_popcountll
  17. using namespace std;
  18. template<class X,class Y>
  19.     void minimize(X &x,const Y &y) {
  20.         if (x>y) x=y;
  21.     }
  22. template<class X,class Y>
  23.     void maximize(X &x,const Y &y) {
  24.         if (x<y) x=y;
  25.     }
  26. template<class T>
  27.     T Abs(const T &x) {
  28.         return (x<0?-x:x);
  29.     }
  30.  
  31. /* Author: Van Hanh Pham - skyvn97 */
  32.  
  33. /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
  34.  
  35. #define MAX_SIZE   125125
  36. #define MAX_QUERY   250250
  37. const int MAX_NEED = (int)1e9 + 7;
  38. const long long MAX_BUDGET = (long long)1e18 + 7LL;
  39.  
  40. class SegmentTree {
  41.     private:
  42.     int cnt[MASK(18) + 7];
  43.     long long sum[MASK(18) + 7];
  44.     int n;
  45.  
  46.     public:
  47.     SegmentTree(int _n = 0) {
  48.         n = _n;
  49.         memset(cnt, 0, sizeof cnt);
  50.         memset(sum, 0, sizeof sum);
  51.     }
  52.  
  53.     void reset(void) {
  54.         memset(cnt, 0, sizeof cnt);
  55.         memset(sum, 0, sizeof sum);
  56.     }
  57.  
  58.     void add(int pos, int capa, int cost) {
  59.         int i = 1, l = 1, r = n;
  60.         while (true) {
  61.             cnt[i] += capa;
  62.             sum[i] += 1LL * capa * cost;
  63.             minimize(cnt[i], MAX_NEED);
  64.             minimize(sum[i], MAX_BUDGET);
  65.  
  66.             if (l == r) return;
  67.  
  68.             int m = (l + r) >> 1;
  69.             if (pos > m) {
  70.                 i = 2 * i + 1; l = m + 1;
  71.             } else {
  72.                 i = 2 * i; r = m;
  73.             }
  74.         }
  75.     }
  76.  
  77.     bool haveEnough(int need, long long budget) const {
  78.         if (cnt[1] < need) return false;
  79.         int i = 1, l = 1, r = n;
  80.  
  81.         while (true) {
  82.             if (l == r) return sum[i] / cnt[i] * need <= budget;
  83.  
  84.             int m = (l + r) >> 1;
  85.             if (cnt[2 * i] == need) return sum[2 * i] <= budget;
  86.             if (cnt[2 * i] > need) {
  87.                 i = 2 * i; r = m;
  88.             } else {
  89.                 budget -= sum[2 * i];
  90.                 if (budget < 0) return false;
  91.                 need -= cnt[2 * i];
  92.                 i = 2 * i + 1; l = m + 1;
  93.             }
  94.         }
  95.     }
  96. };
  97.  
  98. struct Store {
  99.     int place, have, price;
  100.  
  101.     Store() {
  102.         place = have = price = 0;
  103.     }
  104.  
  105.     void input(void) {
  106.         scanf("%d%d%d", &place, &have, &price);
  107.     }
  108.  
  109.     bool operator < (const Store &s) const {
  110.         return price < s.price;
  111.     }
  112. };
  113.  
  114. struct Query {
  115.     int need, low, high;
  116.     long long budget;
  117.  
  118.     Query(int _need = 0, long long _budget = 0) {
  119.         need = _need; budget = _budget; low = high = 0;
  120.     }
  121. };
  122.  
  123. #define MAX_QUERY_NODE   15
  124.  
  125. vector<int> adj[MAX_SIZE];
  126. int dist[MAX_QUERY_NODE + 3][MAX_SIZE];
  127. pair<int, int> storesByDist[MAX_SIZE];
  128. Store stores[MAX_SIZE];
  129. int numNode, numEdge, numStore, numQuery;
  130. SegmentTree myit;
  131. Query queries[MAX_QUERY];
  132. vector<int> queryID[MAX_SIZE];
  133. vector<pair<int, int>> asks;
  134.  
  135. void init(void) {
  136.     scanf("%d%d", &numNode, &numEdge);
  137.     REP(love, numEdge) {
  138.         int u, v; scanf("%d%d", &u, &v);
  139.         adj[u].push_back(v);
  140.         adj[v].push_back(u);
  141.     }
  142.  
  143.     scanf("%d", &numStore);
  144.     FOR(i, 1, numStore) stores[i].input();
  145.     sort(stores + 1, stores + numStore + 1);
  146.  
  147.     scanf("%d", &numQuery);
  148.     FOR(i, 1, numQuery) {
  149.         int place, need; long long budget;
  150.         scanf("%d%d%lld", &place, &need, &budget);
  151.         queries[i] = Query(need, budget);
  152.         queryID[place].push_back(i);
  153.     }
  154. }
  155.  
  156. void bfs(int s, int dist[]) {
  157.     queue<int> q;
  158.     dist[s] = 0; q.push(s);
  159.     while (!q.empty()) {
  160.         int u = q.front(); q.pop();
  161.         FORE(it, adj[u]) if (dist[*it] > numNode) {
  162.             dist[*it] = dist[u] + 1;
  163.             q.push(*it);
  164.         }
  165.     }
  166. }
  167. void prepare(void) {
  168.     memset(dist, 0x3f, sizeof dist);
  169.     FOR(i, 1, MAX_QUERY_NODE) bfs(i, dist[i]);
  170.     myit = SegmentTree(numStore);
  171. }
  172.  
  173. void answerQuery(int place) {
  174.     if (queryID[place].empty()) return;
  175.  
  176.     FOR(i, 1, numStore) storesByDist[i] = make_pair(dist[place][stores[i].place], i);
  177.     sort(storesByDist + 1, storesByDist + numStore + 1);
  178.  
  179.     FORE(it, queryID[place]) {
  180.         queries[*it].low = 0;
  181.         queries[*it].high = numNode;
  182.     }
  183.  
  184.     while (true) {
  185.         asks.clear();
  186.         FORE(it, queryID[place]) {
  187.             int low = queries[*it].low, high = queries[*it].high;
  188.             if (low == high) continue;
  189.             asks.push_back(make_pair(high - low == 1 ? low : (low + high) >> 1, *it));
  190. //            if (*it == 4) printf("CHECK POINT %d\n", high - low == 1 ? low : (low + high) >> 1);
  191.         }
  192.         if (asks.empty()) break;
  193.  
  194.         myit.reset();
  195.         sort(ALL(asks));
  196.         int j = 1;
  197.  
  198.         FORE(it, asks) {
  199.             while (j <= numStore) {
  200.                 int k = storesByDist[j].se;
  201.                 if (dist[place][stores[k].place] > it->fi) break;
  202.                 myit.add(k, stores[k].have, stores[k].price);
  203. //                printf("ADD pos %d, capa %d, price %d\n", k, stores[k].have, stores[k].price);
  204.                 j++;
  205.             }
  206.  
  207. //            if (it->se == 4) printf("Checking need %d, budget %lld\n", queries[it->se].need, queries[it->se].budget);
  208.             if (myit.haveEnough(queries[it->se].need, queries[it->se].budget)) queries[it->se].high = it->fi;
  209.             else queries[it->se].low = it->fi + 1;
  210.         }
  211.     }
  212. }
  213.  
  214. void process(void) {
  215.     FOR(i, 1, MAX_QUERY_NODE) answerQuery(i);
  216.     FOR(i, 1, numQuery) printf("%d ", queries[i].low < numNode ? queries[i].low : -1);
  217.     printf("\n");
  218. }
  219.  
  220. int main(void) {
  221. #ifdef ONLINE_JUDGE
  222.     freopen("shipping.inp", "r", stdin);
  223.     freopen("shipping.out", "w", stdout);
  224. #endif // ONLINE_JUDGE
  225.     init();
  226.     prepare();
  227.     process();
  228.     return 0;
  229. }
  230. /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
Success #stdin #stdout 0.01s 32772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TOEV5Q
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!