CSES - IZhO 2017, day 2 - Results
Submission details
Task:Hard route
Sender:Yytsi
Submission time:2019-02-11 11:18:02 +0200
Language:C++
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'void h2(int, int)':
input/code.cpp:38:20: error: 'class std::unordered_map<int, int>' has no member named 'rbegin'; did you mean 'begin'?
       auto it = am.rbegin();
                    ^~~~~~
                    begin
input/code.cpp:68:20: error: 'class std::unordered_map<int, int>' has no member named 'rbegin'; did you mean 'begin'?
       auto it = am.rbegin();
                    ^~~~~~
                    begin

Code

// ollpun koodi, testaan vain




#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
vector<int> v[500000];
vector<pair<int, int>> ov[500000];
long mv = 0, mc = 0;
pair<int, int> h1(int i, int p=-1) {
  ov[i].reserve(v[i].size());
  pair<int, int> trt{0, 1};
  for (int j : v[i]) {
    if (j == p) continue;
    auto cv = h1(j, i);
    ov[i].push_back(cv);
    if (cv.F > trt.F) trt = {cv.F, 0};
    if (cv.F == trt.F) trt.S += cv.S;
  }
  trt.F++;
  return trt;
}
void h2(int i, int p=-1) {
  {
    unordered_map<int, int> am;
    auto &chv = ov[i];
    for (auto cv : chv) {
      am[cv.F] += cv.S;
    }
    if (v[i].size() == 1) am[0] = 1;
    int xi = 0;
    for (int j : v[i]) {
      if (j == p) continue;
      am[chv[xi].F] -= chv[xi].S;
      auto it = am.rbegin();
      pair<int, int> gp = *it;
      if (gp.S == 0) {
        it++, gp = *it;
      }
      gp.F++;
      ov[j].push_back(gp);
      am[chv[xi].F] += chv[xi].S;
      xi++;
    }
  }
  for (int j : v[i]) {
    if (j == p) continue;
    h2(j, i);
  }
  if (v[i].size() == 1) return;
  {
    unordered_map<int, int> uq, am;
    auto &chv = ov[i];
    for (auto cv : chv) {
      uq[cv.F]++;
      am[cv.F] += cv.S;
    }
    for (auto cv : chv) {
      am[cv.F] -= cv.S;
      if (am[cv.F] == 0) am.erase(cv.F);
      uq[cv.F]--;
      
      int opc = min(2, int(am.size()));
      int ops[2];
      auto it = am.rbegin();
      for (int cc = 0; cc < opc; ++cc, ++it) {
        ops[cc] = it->F;
      }
      for (int cc = 0; cc < opc; ++cc) {
        int co = ops[cc];
        uq[co]--;
        int sup = 0;
        for (int cc2 = 0; cc2 < opc; ++cc2) {
          if (uq[ops[cc2]]) sup = max(sup, ops[cc2]);
        }
        long rv = long(co+cv.F)*sup;
        if (rv > mv) mv = rv, mc = 0;
        if (rv == mv) mc += long(cv.S)*am[co];
        uq[co]++;
      }
      am[cv.F] += cv.S;
      uq[cv.F]++;
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n-1; ++i) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  h1(0);
  h2(0);
  if (mv == 0) mc = 2;
  cout << mv << " " << mc/2 << endl;
}