Submission #716530

#TimeUsernameProblemLanguageResultExecution timeMemory
716530KINGDynamic Diameter (CEOI19_diameter)C++14
24 / 100
5073 ms10984 KiB
#include<bits/stdc++.h> #define NOT_STONKS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 2e5 + 10; //4e6 + 10; //3e5 + 10; const int mod = 1e9 + 7; //998244353; typedef long long ll; ll n, q, w, f[maxn], s[maxn], dis[maxn]; vector< pair<ll, ll> > adj[maxn]; pair<ll, ll> temp; pair< pair<ll, ll>, ll > edge[maxn]; void trav(int v, int par = -1) { for (auto [ u, x ] : adj[v]) if (u != par) { dis[u] = dis[v] + x; temp = max(temp, { dis[u], u }); trav(u, v); } } int main() { NOT_STONKS; cin >> n >> q >> w; for (int i = 0; i < n - 1; i++) { int u, v, x; cin >> u >> v >> x; edge[i] = { { u, v }, x }; adj[u].push_back({ v, x }); adj[v].push_back({ u, x }); } ll last = 0; if (adj[1].size() == n - 1) { multiset<ll> m; for (auto [ u, _ ] : adj[1]) m.insert(_); while (q--) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; int E = max(edge[d].first.first, edge[d].first.second); int t0 = adj[E].back().first, t1 = adj[E].back().second; m.erase(m.find(t1)); adj[E].pop_back(); adj[E].push_back({ t0, e }); m.insert(e); multiset<ll>::iterator it = m.begin(); last = *it; if (it != m.end()) { it++; last += *it; } cout << last << '\n'; } } else { while (q--) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; auto E = edge[d]; int id1 = find(adj[E.first.first].begin(), adj[E.first.first].end(), make_pair(E.first.second, E.second)) - adj[E.first.first].begin(); int id2 = find(adj[E.first.second].begin(), adj[E.first.second].end(), make_pair(E.first.first, E.second)) - adj[E.first.second].begin(); adj[E.first.first].erase(adj[E.first.first].begin() + id1); adj[E.first.second].erase(adj[E.first.second].begin() + id2); edge[d] = { E.first, e }; adj[E.first.first].push_back({ E.first.second, e }); adj[E.first.second].push_back({ E.first.first, e }); temp = { 0, 0 }; dis[1] = 0; trav(1); dis[temp.second] = 0; trav(temp.second); last = temp.first; cout << last << '\n'; } } return 0; }

Compilation message (stderr)

diameter.cpp: In function 'void trav(int, int)':
diameter.cpp:16:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for (auto [ u, x ] : adj[v]) if (u != par) {
      |               ^
diameter.cpp: In function 'int main()':
diameter.cpp:36:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   36 |     if (adj[1].size() == n - 1) {
      |         ~~~~~~~~~~~~~~^~~~~~~~
diameter.cpp:38:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto [ u, _ ] : adj[1])
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...