fork download
copy 
  1. //Problem arb4 @ 27-06-2015
  2. #include <algorithm>
  3. #include <fstream>
  4. #include <iostream>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. ifstream fin("arb4.in");
  10. ofstream fout("arb4.out");
  11.  
  12.  
  13. #define kMaxChar 1000000
  14. #define verf ((++BufferChar >= kMaxChar) ? (fin.read(Buffer, kMaxChar), BufferChar = 0) : (1))
  15.  
  16. int BufferChar = kMaxChar;
  17. char Buffer[kMaxChar];
  18.  
  19. void getInt (int &a) {
  20.     if (BufferChar >= kMaxChar)
  21.         verf;
  22.     bool minus = false;
  23.     for ( ;!((Buffer[BufferChar] >= '0' && Buffer[BufferChar] <= '9') || (Buffer [BufferChar] == '-')); verf)
  24.         ;
  25.     if (Buffer[BufferChar] == '-') {
  26.         verf;
  27.         minus = true;
  28.     }
  29.     for (a = 0; (Buffer[BufferChar] >= '0' && Buffer[BufferChar] <= '9'); a *= 10,a += (Buffer[BufferChar] - '0'), verf)
  30.         ;
  31.     if (minus)
  32.         a *= -1;
  33.     return ;
  34. }
  35.  
  36.  
  37. const int kMaxN = 3e5 + 5, kLog = 20;
  38.  
  39. #define int64 long long
  40.  
  41.  
  42. int father[kLog][kMaxN];
  43. int fatherEdge[kMaxN];
  44.  
  45. pair<int, int> edge[kMaxN];
  46. vector<int> edges[kMaxN];
  47. int rez[kMaxN], cost[kMaxN];
  48.  
  49. int deep[kMaxN];
  50. bool viz[kMaxN];
  51.  
  52. int other(int ind, int nod) {
  53.     return edge[ind].first + edge[ind].second - nod;
  54. }
  55.  
  56. void df(int nod) {
  57.     viz[nod] = true;
  58.     for (auto itr : edges[nod]) {
  59.         int oth = other(itr, nod);
  60.         if (not viz[oth]) {
  61.             deep[oth] = deep[nod] + 1;
  62.             father[0][oth] = nod;
  63.             fatherEdge[oth] = itr;
  64.             df(oth);
  65.         }
  66.     }
  67. }
  68.  
  69. int lca(int a, int b) {
  70.     if (a == b) {
  71.         return a;
  72.     }
  73.     if (deep[a] < deep[b]) {
  74.         swap(a, b);
  75.     }
  76.  
  77.     for (int p = kLog - 1; p >= 0; --p) {
  78.         if (deep[a] - (1 << p) >= deep[b]) {
  79.             a = father[p][a];
  80.         }
  81.     }
  82.  
  83.     if (a == b) {
  84.         return a;
  85.     }
  86.  
  87.     for (int p = kLog - 1; p >= 0; --p) {
  88.         if (father[p][a] != father[p][b]) {
  89.             a = father[p][a];
  90.             b = father[p][b];
  91.         }
  92.     }
  93.     return father[0][a];
  94. }
  95.  
  96. pair<int, int> qEdge[kMaxN];
  97. int qCost[kMaxN];
  98.  
  99. bool stillGoodUp[kMaxN];
  100. int nextUp[kMaxN];
  101.  
  102. int goUp(int nod, int minD, int _rez) {
  103.     if (deep[nod] <= minD) {
  104.         return nod;
  105.     }
  106.  
  107.     if (stillGoodUp[nod] == true) {
  108.         rez[fatherEdge[nod]] = _rez;
  109.         stillGoodUp[nod] = false;
  110.     }
  111.     nextUp[nod] = goUp(nextUp[nod], minD, _rez);
  112.     return nextUp[nod];
  113. }
  114.  
  115. int main() {
  116.     int n, m; 
  117. //    fin >> n >> m;
  118.     getInt(n); getInt(m);
  119.     m -= n - 1;
  120.     for (int i = 1; i < n; ++i) {
  121. //	    fin >> edge[i].first >> edge[i].second >> cost[i];
  122.         getInt(edge[i].first); getInt(edge[i].second); getInt(cost[i]);
  123.         edges[edge[i].first].push_back(i);
  124.         edges[edge[i].second].push_back(i);
  125.     }
  126.  
  127.     df(0);
  128.     for (int i = 1; i < n; ++i) {
  129.         stillGoodUp[i] = true;
  130.         nextUp[i] = father[0][i];
  131.     }
  132.  
  133.     for (int l = 1; l < kLog; ++l) {
  134.         for (int i = 0; i < n; ++i) {
  135.             father[l][i] = father[l - 1][father[l - 1][i]];
  136.         }
  137.     }
  138.  
  139.     vector<pair<int, int> > events;
  140.     for (int i = 1; i <= m; ++i) {
  141. //        fin >> qEdge[i].first >> qEdge[i].second >> qCost[i];
  142.         getInt(qEdge[i].first); getInt(qEdge[i].second); getInt(qCost[i]);
  143.         events.push_back(make_pair(qCost[i], i));
  144.     }
  145.     sort(events.begin(), events.end());
  146.  
  147.     for (int i = 1; i < n; ++i) {
  148.         rez[i] =  -1 -n + 2;
  149.     }
  150.  
  151.     for (auto itr : events) {
  152.         int ind = itr.second;
  153.         int a = qEdge[ind].first;
  154.         int b = qEdge[ind].second;
  155.         int l = lca(a, b);
  156.  
  157.         int dl = deep[l];
  158.  
  159.         goUp(a, dl, ind);
  160.         goUp(b, dl, ind);
  161.     }
  162.  
  163.     for (int i = 1; i < n; ++i) {
  164.         fout << rez[i] + n - 2 << '\n';
  165.     }
  166.     return 0;
  167. }
Time limit exceeded #stdin #stdout 5s 43512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Kk0h9R
language:
C++14 (gcc 8.3)
created:
8 years 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!