제출 #275951

#제출 시각아이디문제언어결과실행 시간메모리
275951theStaticMindDynamic Diameter (CEOI19_diameter)C++14
36 / 100
5051 ms35152 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 #define int long long int using namespace std; int n; vector<ii> adj[100005]; vector<ii> edge; int anc[20][100005]; int depth[100005]; multiset<int> diameter; multiset<int> data[100005]; map<int, int> ptr; int getedge(int x, int y){ return lower_bound(all(adj[x]), ii{y, -1}) - adj[x].begin(); } int getdia(int x){ if(data[x].empty()) return 0; if(data[x].size() == 1) return *data[x].rbegin(); return *data[x].rbegin() + *++data[x].rbegin(); } int getmax(int x){ if(data[x].empty()) return 0; return *data[x].rbegin(); } void update(int x, int y){ diameter.erase(diameter.find(getdia(x))); data[x].erase(data[x].lower_bound(ptr[y])); ptr[y] = getmax(y) + adj[x][getedge(x, y)].second; data[x].insert(ptr[y]); diameter.insert(getdia(x)); } void init(int x, int pre){ for(auto p : adj[x]){ int y = p.first; if(y == pre) continue; anc[0][y] = x; depth[y] = depth[x] + 1; init(y, x); data[x].insert(getmax(y) + p.second); ptr[y] = getmax(y) + p.second; } diameter.insert(getdia(x)); } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int q, W; cin >> n >> q >> W; for(int i = 0; i < n - 1; i++){ int x, y, z; cin >> x >> y >> z; adj[x].pb({y, z}); adj[y].pb({x, z}); edge.pb({x, y}); } for(int i = 1; i <= n; i++){ sort(all(adj[i])); } init(1, 0); int last = 0; while(q--){ ii p; cin >> p.first >> p.second; p.first = (p.first + last) % (n - 1); p.second = (p.second + last) % W; int x = edge[p.first].first; int y = edge[p.first].second; int z = p.second; adj[x][getedge(x, y)].second = z; adj[y][getedge(y, x)].second = z; if(depth[x] > depth[y]) swap(x, y); while(x){ update(x, y); y = x; x = anc[0][x]; } last = *diameter.rbegin(); cout << last << "\n"; } }
#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...