# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
275881 | 2020-08-20T08:13:28 Z | AKaan37 | Dynamic Diameter (CEOI19_diameter) | C++17 | 2121 ms | 25192 KB |
//Bismillahirrahmanirrahim //█▀█─█──█──█▀█─█─█ //█▄█─█──█──█▄█─█▄█ //█─█─█▄─█▄─█─█─█─█ #include <bits/stdc++.h> using namespace std; typedef long long lo; typedef pair< lo,lo > PII; #define fi first #define se second #define mp make_pair #define int long long #define endl "\n" #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) #define ort ((bas+son)/2) const lo inf = 1000000000000000000; const lo KOK = 100000; const lo LOG = 30; const lo li = 500005; const lo mod = 1000000007; int n,m,b[li],a[li],k,flag,t,x[li],y[li],z[li],mx,ind; int cev; multiset<int> st; string s; vector<PII> v[li]; inline void dfs(int node,int ata,int der){ for(int i=0;i<(int)v[node].size();i++){ int go=v[node][i].fi; int co=v[node][i].se; if(go==ata)continue; dfs(go,node,der+co); } if(der>mx)ind=node; mx=max(mx,der); } int32_t main(void){ scanf("%lld %lld %lld",&n,&t,&k); for(int i=1;i<n;i++){ scanf("%lld %lld %lld",&x[i],&y[i],&z[i]); st.insert(z[i]); } if(n*t<=5000*5000){ while(t--){ int d,e; scanf("%lld %lld",&d,&e); z[(d+cev)%(n-1)+1]=(cev+e)%k; FOR v[i].clear(); for(int i=1;i<n;i++){ v[x[i]].pb({y[i],z[i]}); v[y[i]].pb({x[i],z[i]}); } mx=0; dfs(1,0,0); mx=0; dfs(ind,0,0); cev=mx; printf("%lld\n",cev); } return 0; } while(t--){ int d,e; scanf("%lld %lld",&d,&e); st.erase(st.find(z[(d+cev)%(n-1)+1])); z[(d+cev)%(n-1)+1]=(cev+e)%k; st.insert(z[(d+cev)%(n-1)+1]); auto it=st.end(); if(it==st.begin()){cev=0;printf("%lld\n",cev);continue;} it--; cev=*it; if(it==st.begin()){printf("%lld\n",cev);continue;} it--; cev+=*it; printf("%lld\n",cev); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12032 KB | Output is correct |
2 | Correct | 9 ms | 12032 KB | Output is correct |
3 | Correct | 8 ms | 12032 KB | Output is correct |
4 | Correct | 10 ms | 12032 KB | Output is correct |
5 | Correct | 8 ms | 12032 KB | Output is correct |
6 | Correct | 8 ms | 12032 KB | Output is correct |
7 | Correct | 9 ms | 12032 KB | Output is correct |
8 | Correct | 9 ms | 12032 KB | Output is correct |
9 | Correct | 8 ms | 12032 KB | Output is correct |
10 | Correct | 10 ms | 12160 KB | Output is correct |
11 | Correct | 9 ms | 12032 KB | Output is correct |
12 | Correct | 9 ms | 12032 KB | Output is correct |
13 | Correct | 9 ms | 12032 KB | Output is correct |
14 | Correct | 9 ms | 12032 KB | Output is correct |
15 | Correct | 9 ms | 12032 KB | Output is correct |
16 | Correct | 9 ms | 12032 KB | Output is correct |
17 | Correct | 9 ms | 12032 KB | Output is correct |
18 | Correct | 9 ms | 12160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12032 KB | Output is correct |
2 | Correct | 9 ms | 12032 KB | Output is correct |
3 | Correct | 8 ms | 12032 KB | Output is correct |
4 | Correct | 10 ms | 12032 KB | Output is correct |
5 | Correct | 8 ms | 12032 KB | Output is correct |
6 | Correct | 8 ms | 12032 KB | Output is correct |
7 | Correct | 9 ms | 12032 KB | Output is correct |
8 | Correct | 9 ms | 12032 KB | Output is correct |
9 | Correct | 8 ms | 12032 KB | Output is correct |
10 | Correct | 10 ms | 12160 KB | Output is correct |
11 | Correct | 9 ms | 12032 KB | Output is correct |
12 | Correct | 9 ms | 12032 KB | Output is correct |
13 | Correct | 9 ms | 12032 KB | Output is correct |
14 | Correct | 9 ms | 12032 KB | Output is correct |
15 | Correct | 9 ms | 12032 KB | Output is correct |
16 | Correct | 9 ms | 12032 KB | Output is correct |
17 | Correct | 9 ms | 12032 KB | Output is correct |
18 | Correct | 9 ms | 12160 KB | Output is correct |
19 | Correct | 264 ms | 12400 KB | Output is correct |
20 | Correct | 268 ms | 12280 KB | Output is correct |
21 | Correct | 317 ms | 12280 KB | Output is correct |
22 | Correct | 318 ms | 12288 KB | Output is correct |
23 | Correct | 1729 ms | 12920 KB | Output is correct |
24 | Correct | 1950 ms | 13144 KB | Output is correct |
25 | Correct | 1962 ms | 13060 KB | Output is correct |
26 | Correct | 2121 ms | 13428 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12160 KB | Output is correct |
2 | Correct | 9 ms | 12032 KB | Output is correct |
3 | Correct | 10 ms | 12160 KB | Output is correct |
4 | Correct | 30 ms | 12288 KB | Output is correct |
5 | Correct | 115 ms | 12556 KB | Output is correct |
6 | Correct | 8 ms | 12032 KB | Output is correct |
7 | Correct | 9 ms | 12160 KB | Output is correct |
8 | Correct | 12 ms | 12160 KB | Output is correct |
9 | Correct | 45 ms | 12196 KB | Output is correct |
10 | Correct | 329 ms | 12556 KB | Output is correct |
11 | Correct | 85 ms | 12536 KB | Output is correct |
12 | Correct | 15 ms | 12672 KB | Output is correct |
13 | Correct | 44 ms | 12672 KB | Output is correct |
14 | Correct | 313 ms | 12832 KB | Output is correct |
15 | Correct | 25 ms | 12544 KB | Output is correct |
16 | Correct | 80 ms | 13432 KB | Output is correct |
17 | Correct | 167 ms | 25192 KB | Output is correct |
18 | Correct | 723 ms | 25064 KB | Output is correct |
19 | Correct | 92 ms | 20344 KB | Output is correct |
20 | Correct | 135 ms | 20728 KB | Output is correct |
21 | Correct | 390 ms | 22136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 12160 KB | Output is correct |
2 | Correct | 370 ms | 12540 KB | Output is correct |
3 | Incorrect | 41 ms | 12408 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 296 ms | 20600 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12032 KB | Output is correct |
2 | Correct | 9 ms | 12032 KB | Output is correct |
3 | Correct | 8 ms | 12032 KB | Output is correct |
4 | Correct | 10 ms | 12032 KB | Output is correct |
5 | Correct | 8 ms | 12032 KB | Output is correct |
6 | Correct | 8 ms | 12032 KB | Output is correct |
7 | Correct | 9 ms | 12032 KB | Output is correct |
8 | Correct | 9 ms | 12032 KB | Output is correct |
9 | Correct | 8 ms | 12032 KB | Output is correct |
10 | Correct | 10 ms | 12160 KB | Output is correct |
11 | Correct | 9 ms | 12032 KB | Output is correct |
12 | Correct | 9 ms | 12032 KB | Output is correct |
13 | Correct | 9 ms | 12032 KB | Output is correct |
14 | Correct | 9 ms | 12032 KB | Output is correct |
15 | Correct | 9 ms | 12032 KB | Output is correct |
16 | Correct | 9 ms | 12032 KB | Output is correct |
17 | Correct | 9 ms | 12032 KB | Output is correct |
18 | Correct | 9 ms | 12160 KB | Output is correct |
19 | Correct | 264 ms | 12400 KB | Output is correct |
20 | Correct | 268 ms | 12280 KB | Output is correct |
21 | Correct | 317 ms | 12280 KB | Output is correct |
22 | Correct | 318 ms | 12288 KB | Output is correct |
23 | Correct | 1729 ms | 12920 KB | Output is correct |
24 | Correct | 1950 ms | 13144 KB | Output is correct |
25 | Correct | 1962 ms | 13060 KB | Output is correct |
26 | Correct | 2121 ms | 13428 KB | Output is correct |
27 | Correct | 8 ms | 12160 KB | Output is correct |
28 | Correct | 9 ms | 12032 KB | Output is correct |
29 | Correct | 10 ms | 12160 KB | Output is correct |
30 | Correct | 30 ms | 12288 KB | Output is correct |
31 | Correct | 115 ms | 12556 KB | Output is correct |
32 | Correct | 8 ms | 12032 KB | Output is correct |
33 | Correct | 9 ms | 12160 KB | Output is correct |
34 | Correct | 12 ms | 12160 KB | Output is correct |
35 | Correct | 45 ms | 12196 KB | Output is correct |
36 | Correct | 329 ms | 12556 KB | Output is correct |
37 | Correct | 85 ms | 12536 KB | Output is correct |
38 | Correct | 15 ms | 12672 KB | Output is correct |
39 | Correct | 44 ms | 12672 KB | Output is correct |
40 | Correct | 313 ms | 12832 KB | Output is correct |
41 | Correct | 25 ms | 12544 KB | Output is correct |
42 | Correct | 80 ms | 13432 KB | Output is correct |
43 | Correct | 167 ms | 25192 KB | Output is correct |
44 | Correct | 723 ms | 25064 KB | Output is correct |
45 | Correct | 92 ms | 20344 KB | Output is correct |
46 | Correct | 135 ms | 20728 KB | Output is correct |
47 | Correct | 390 ms | 22136 KB | Output is correct |
48 | Correct | 45 ms | 12160 KB | Output is correct |
49 | Correct | 370 ms | 12540 KB | Output is correct |
50 | Incorrect | 41 ms | 12408 KB | Output isn't correct |
51 | Halted | 0 ms | 0 KB | - |