Submission #914032

#	Time	Username	Problem	Language	Result	Execution time	Memory
914032		CyberCow	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	1122 ms	58228 KiB

diameter

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);

const ll N = 100010;

vector<pair<int, ll>> v[N];
int n;

pair<ll, ll> Dfs(int g, int p)
{
    ll maher = 0, ind = g;
    for (auto to : v[g])
    {
        if (to.first != p)
        {
            pair<ll, ll> x = Dfs(to.first, g);
            if (to.second + x.second >= maher)
            {
                maher = to.second + x.second;
                ind = x.first;
            }
        }
    }
    return { ind, maher };
}

ll get_diam()
{
    return Dfs(Dfs(1, -1).first, -1).second;
}


vector<ll> karuc;
int tin[N], tout[N], ti = 0;

pair<int, int> s[8 * N];

void build(int p, int lp, int rp)
{
    if (lp == rp)
    {
        s[p] = { karuc[lp], 0 };
        return;
    }
    int m = (lp + rp) / 2;
    build(p * 2, lp, m);
    build(p * 2 + 1, m + 1, rp);
    s[p].first = max(s[p * 2].first, s[p * 2 + 1].first);
    if (s[p].first == s[p * 2].first)
        s[p].second = max(s[p * 2].second, s[p * 2 + 1].first);
    else
        s[p].second = max(s[p * 2].first, s[p * 2 + 1].second);
}

void Dfs1(int g, int p, ll her)
{
    karuc.push_back(her);
    tin[g] = ti++;
    for (auto to : v[g])
    {
        if (to.first != p)
        {
            Dfs1(to.first, g, her + to.second);
        }
    }
    tout[g] = ti++;
    karuc.push_back(her);
}

bool papaya(int a, int b)
{
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

ll ly[8 * N];

void push(int p)
{
    ly[p * 2] += ly[p];
    ly[p * 2 + 1] += ly[p];
    s[p * 2].first = max(s[p * 2].first + ly[p], 0LL);
    s[p * 2].second = max(s[p * 2].second + ly[p], 0LL);
    s[p * 2 + 1].first = max(s[p * 2 + 1].first + ly[p], 0LL);
    s[p * 2 + 1].second = max(s[p * 2 + 1].second + ly[p], 0LL);
    ly[p] = 0;
}

void update(int p, int lp, int rp, int l, int r, ll pox)
{
    if (l > r)
        return;
    if (lp == l && rp == r)
    {
        s[p].first = max(s[p].first + pox, 0LL);
        s[p].second = max(s[p].second + pox, 0LL);
        ly[p] += pox;
        return;
    }
    push(p);
    int m = (lp + rp) / 2;
    update(p * 2, lp, m, l, min(m, r), pox);
    update(p * 2 + 1, m + 1, rp, max(l, m + 1), r, pox);
    s[p].first = max(s[p * 2].first, s[p * 2 + 1].first);
    if (s[p].first == s[p * 2].first)
        s[p].second = max(s[p * 2].second, s[p * 2 + 1].first);
    else
        s[p].second = max(s[p * 2].first, s[p * 2 + 1].second);
}

void solve()
{
    ll q, w, i, j, x, y, z;
    cin >> n >> q >> w;
    if (n <= 5000 && q <= 5000 && w <= 10000)
    {
        vector<pair<ll, ll>> kox;
        for (i = 0; i < n - 1; i++)
        {
            cin >> x >> y >> z;
            kox.push_back({ x, y });
            v[x].push_back({ y, z });
            v[y].push_back({ x, z });
        }
        for (i = 0; i <= n; i++)
        {
            sort(v[i].begin(), v[i].end());
        }
        ll last = 0;
        for (i = 0; i < q; i++)
        {
            cin >> x >> y;
            x = (x + last) % (n - 1);
            y = (y + last) % w;
            int x1 = kox[x].first;
            int y1 = kox[x].second;
            v[x1][lower_bound(v[x1].begin(), v[x1].end(), make_pair(y1, 0LL)) - v[x1].begin()].second = y;
            v[y1][lower_bound(v[y1].begin(), v[y1].end(), make_pair(x1, 0LL)) - v[y1].begin()].second = y;
            last = get_diam();
            cout << last << '\n';
        }
        return;
    }
    vector<pair<ll, pair<ll, ll>>> kox;
    multiset<ll> se;
    int st = 1;
    for (i = 0; i < n - 1; i++)
    {
        cin >> x >> y >> z;
        if (x != 1 && y != 1)
            st = 0;
        kox.push_back({ z, {x, y} });
        v[x].push_back({ y, z });
        v[y].push_back({ x, z });
        se.insert(z);
    }
    //st = 0;////////
    if (st)
    {
        ll last = 0;
        for (i = 0; i < q; i++)
        {
            cin >> x >> y;
            x = (x + last) % (n - 1);
            y = (y + last) % w;
            int x1 = kox[x].second.first;
            int y1 = kox[x].second.second;
            se.erase(se.find(kox[x].first));
            se.insert(y);
            kox[x].first = y;
            last = *--se.end();
            if (se.size() != 1)
                last += *----se.end();
            cout << last << '\n';
        }
        return;
    }
    Dfs1(1, -1, 0);
    build(1, 0, ti - 1);//
    ll last = 0;
    for (i = 0; i < q; i++)
    {
        cin >> x >> y;
        x = (x + last) % (n - 1);
        y = (y + last) % w;
        int x1 = kox[x].second.first;
        int y1 = kox[x].second.second;
        int poxgag = x1;
        if (papaya(x1, y1))
        {
            poxgag = y1;
        }
        update(1, 0, ti - 1, tin[poxgag], tout[poxgag], y - kox[x].first);
        kox[x].first = y;
        last = s[1].first + s[1].second;
        cout << last << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void solve()':
diameter.cpp:188:17: warning: unused variable 'x1' [-Wunused-variable]
  188 |             int x1 = kox[x].second.first;
      |                 ^~
diameter.cpp:189:17: warning: unused variable 'y1' [-Wunused-variable]
  189 |             int y1 = kox[x].second.second;
      |                 ^~
diameter.cpp:135:17: warning: unused variable 'j' [-Wunused-variable]
  135 |     ll q, w, i, j, x, y, z;
      |                 ^

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