fork download
copy 
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20. #include <chrono>
  21. #include <cstring>
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26.  
  27. #ifdef iq
  28.   mt19937 rnd(228);
  29. #else
  30.   mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  31. #endif
  32.  
  33. int main() {
  34. #ifdef iq
  35.   freopen("a.in", "r", stdin);
  36. #endif
  37.   ios::sync_with_stdio(0);
  38.   cin.tie(0);
  39.   int t;
  40.   cin >> t;
  41.   while (t--) {
  42.     int n;
  43.     cin >> n;
  44.     vector <int> ws;
  45.     for (int i = 1; i < n; i++) {
  46.       int a, b, w;
  47.       cin >> a >> b >> w;
  48.       a--, b--;
  49.       ws.push_back(w);
  50.     }
  51.     sort(ws.begin(), ws.end());
  52.     reverse(ws.begin(), ws.end());
  53.     multiset <int> q;
  54.     for (int i = 0; i < n; i++) {
  55.       int x;
  56.       cin >> x;
  57.       q.insert(x);
  58.     }
  59.     int ok = ws[0];
  60.     int cost = 0;
  61.     for (int it = 0; it < 2; it++) {
  62.       if (*q.rbegin() < ok) {
  63.         q.erase(q.begin());
  64.         cost++;
  65.       } else {
  66.         q.erase(q.lower_bound(ok));
  67.       }
  68.     }
  69.     ws.erase(ws.begin());
  70.     for (int x : ws) {
  71.       if (*q.rbegin() >= x) {
  72.         q.erase(q.lower_bound(x)); 
  73.       } else {
  74.         q.erase(q.begin());
  75.         cost++;
  76.       }
  77.     }
  78.     cout << cost << '\n';
  79.   }
  80. }
Time limit exceeded #stdin #stdout 5s 5084KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/URGMJ7
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!