Submission #201699

#	Time	Username	Problem	Language	Result	Execution time	Memory
201699		MiricaMatei	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	5084 ms	255676 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

struct Node {
  long long maxim;
  long long lazy;

  Node() {
    maxim = lazy = 0;
  }
};

class SegTree {
 public:
  int n;
  Node* aint;

  void init(int _n, vector<long long>v) {
    n = _n;
    aint = new Node[4 * n + 5];
    for (int i = 0; i < v.size(); ++i)
      update(1, 1, n, i + 1, v[i]);
  }

  void update(int node, int l, int r, int pos, long long val) {
    if (l == r) {
      aint[node].maxim = val;
      aint[node].lazy = 0;
      return ;
    }
    int m = (l + r) / 2;
    if (pos <= m)
      update(2 * node, l, m, pos, val);
    else
      update(2 * node + 1, m + 1, r, pos, val);
    aint[node] = join(aint[2 * node], aint[2 * node + 1]);
  }

  void updateL(int node, int l, int r, int x, int y, long long val) {
    if (x <= l && r <= y) {
      aint[node].lazy += val;
      propag(node, r - l + 1);
      return ;
    }
    propag(node, r - l + 1);
    if (r < x)
      return ;
    if (l > y)
      return ;
    int m = (r + l) / 2;
    updateL(2 * node, l, m, x, y, val);
    updateL(2 * node + 1, m + 1, r, x, y, val);
    aint[node] = join(aint[2 * node], aint[2 * node + 1]);
  }

  long long query() {
    propag(1, n);
    return aint[1].maxim;
  }

  Node join(Node a, Node b) {
    Node aux;
    aux.maxim = max(a.maxim, b.maxim);
    aux.lazy = 0;
    return aux;
  }

  void propag(int node, int len) {
    aint[node].maxim += aint[node].lazy;
    if (len > 1) {
      aint[2 * node].lazy += aint[node].lazy;
      aint[2 * node + 1].lazy += aint[node].lazy;
    }
    aint[node].lazy = 0;
  }

  void updL(pair<int, int>aux, long long val) {
    updateL(1, 1, n, aux.first, aux.second, val);
  }
};

class Comp {
 public:
   vector<SegTree>v1;
   vector<vector< pair<int, int> > >v2;
   multiset<long long>s1;
} cp[MAXN];

multiset<long long>ans1;
map<pair<int, int>, int>mp;
map<pair<int, int>, pair<int, int> >posComp;
vector<int>wComp[MAXN];
set<pair<int, long long> >G[MAXN];
long long cost[MAXN];

int tsz;
int sz[MAXN];

void getSize(int v, int f) {
  sz[v] = 1;
  for (auto it:G[v])
    if (it.first != f) {
      getSize(it.first, v);
      sz[v] += sz[it.first];
    }
}

int getc(int node, int f) {
  for (auto it:G[node])
    if (it.first != f && tsz / 2 < sz[it.first])
      return getc(it.first, node);
  return node;
}

int k, ind, ind1 = 0;
long long dist[MAXN];
int lin[MAXN], first[MAXN], last[MAXN];
pair<int, pair<int, int> >mc[MAXN];

void dfs1(int node, int f) {
  lin[++ind] = node;
  first[node] = ind;
  for (auto it:G[node])
    if (it.first != f) {
      ind1++;
      int auxind = ind1;
      mc[ind1].first = mp[{it.first, node}];
      mc[ind1].second.first = ind + 1;
      dist[it.first] = dist[node] + it.second;
      dfs1(it.first, node);
      mc[auxind].second.second = ind;
    }
  last[node] = ind;
}

void dfs(int node) {
  getSize(node, 0);
  tsz = sz[node];
  int c = getc(node, 0);
  ++k;
  int j = 0;
  for (auto it:G[c]) {
    j++;
    ind = 0;
    ind1 = 1;
    dist[it.first] = it.second;
    dfs1(it.first, c);
    vector<long long>aux;
    for (int i = 1; i <= ind; ++i)
      aux.push_back(dist[lin[i]]);
    SegTree aux1;
    aux1.init(ind, aux);
    cp[k].v1.push_back(aux1);
    cp[k].s1.insert(aux1.query());
    vector<pair<int, int> >aux2;
    int cmm = mp[{it.first, c}];
    posComp[{k, cmm}] = {j, 1};
    aux2.push_back({1, ind});
    wComp[cmm].push_back(k);
    for (int i = 2; i <= ind1; ++i) {
      posComp[{k, mc[i].first}] = {j, i};
      aux2.push_back(mc[i].second);
      wComp[mc[i].first].push_back(k);
    }
    cp[k].v2.push_back(aux2);
    G[it.first].erase({c, it.second});
  }
  if (!cp[k].s1.empty()) {
    long long ans = 0;
    multiset<long long>::iterator it1 = cp[k].s1.end();
    it1--;
    ans += (*it1);
    if (it1 != cp[k].s1.begin()) {
      it1--;
      ans += (*it1);
    }
    ans1.insert(ans);
  }
  for (auto it:G[c])
    dfs(it.first);
}

void upd(int ed, long long nc) {
  for (auto it:wComp[ed]) {
    pair<int, int>aux = posComp[{it, ed}];
    long long ans = 0;
    multiset<long long>::iterator it1 = cp[it].s1.end();
    it1--;
    ans += (*it1);
    if (it1 != cp[it].s1.begin()) {
      it1--;
      ans += (*it1);
    }
    ans1.erase(ans1.find(ans));
    cp[it].s1.erase(cp[it].s1.find(cp[it].v1[aux.first - 1].query()));
    cp[it].v1[aux.first - 1].updL(cp[it].v2[aux.first - 1][aux.second - 1], nc - cost[ed]);
    cp[it].s1.insert(cp[it].v1[aux.first - 1].query());
    ans = 0;
    it1 = cp[it].s1.end();
    it1--;
    ans += (*it1);
    if (it1 != cp[it].s1.begin()) {
      it1--;
      ans += (*it1);
    }
    ans1.insert(ans);
  }
  cost[ed] = nc;
}

long long qry() {
  multiset<long long>::iterator it = ans1.end();
  it--;
  return (*it);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie();
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  int n, q;
  long long w;
  cin >> n >> q >> w;
  for (int i = 1; i < n; ++i) {
    int x, y;
    long long z;
    cin >> x >> y >> z;
    mp[{x, y}] = mp[{y, x}] = i;
    G[x].insert({y, z});
    G[y].insert({x, z});
    cost[i] = z;
  }

  dfs(1);

  long long last = 0;
  for (int i = 1; i <= q; ++i) {
    int d;
    long long e;
    cin >> d >> e;
    d = (d + last) % (n - 1) + 1;
    e = (e + last) % w;
    upd(d, e);
    last = qry();
    cout << last << '\n';
  }

  return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'void SegTree::init(int, std::vector<long long int>)':
diameter.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27