제출 #971663

#제출 시각아이디문제언어결과실행 시간메모리
971663efedmrlrDynamic Diameter (CEOI19_diameter)C++17
24 / 100
5037 ms17772 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define lli long long int #define MP make_pair #define pb push_back #define REP(i,n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const double EPS = 0.00001; const int INF = 1e9+500; const int N = 3e5+5; const int ALPH = 26; const int LGN = 25; constexpr int MOD = 1e9+7; int n,q,w; vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >()); vector<array<int, 3> > edg(N); vector<int> dist(N); void dfs(int node, int par) { for(auto c : adj[node]) { if(c[0] == par) continue; dist[c[0]] = dist[node] + edg[c[1]][2]; dfs(c[0], node); } } int get_diam() { dist[1] = 0; dfs(1, 0); int ind = 1; for(int i = 1; i <= n; i++) { if(dist[i] > dist[ind]) ind = i; } dist[ind] = 0; dfs(ind, 0); return *max_element(dist.begin(), dist.begin() + n + 1); } inline void solve() { cin >> n >> q >> w; edg.resize(n - 1); REP(i, n - 1) { cin >> edg[i][0] >> edg[i][1] >> edg[i][2]; adj[edg[i][0]].pb({edg[i][1], i}); adj[edg[i][1]].pb({edg[i][0], i}); } int last = 0; REP(z, q) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; edg[d][2] = e; last = get_diam(); cout << last << "\n"; } } signed main() { fastio(); int test = 1; //cin>>test; while(test--) { solve(); } }
#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...