oj.uz

Submission #884753

# Submission time Handle Problem Language Result Execution time Memory
884753 2023-12-08T10:48:17 Z radinr85 Dynamic Diameter (CEOI19_diameter) C++14
31 / 100
 272 ms 22004 KB 
//Radin (you can say Radan)
#include <bits/stdc++.h>

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

typedef long long ll;
typedef deque<int> dq;
typedef long double ld;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;

const int Mx = 101;
const int LOG = 23;
const ll INF = 2e18;
const int maxn = 3e6;
const ll mod = 1e9+7;

#define F first
#define S second
#define endl "\n"
#define lc id << 1
#define pb push_back
#define rc id << 1 | 1
#define all(x) (x).begin(),(x).end()
#define ms(x , y) memset(x , y , sizeof x)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll pw(ll a, ll b, ll md = mod){ll res=1;b=max(b,0ll);while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res%md);}

const int N = 1e5 + 10;
vector<pii> adj[N];
multiset<ll> seti;
ll lazy[N << 2];
ll seg[N << 2];
int col[N];
int st[N];
int fn[N];
int ch[N];
ll w[N];
ll h[N];
int n,q;
ll mx;

void shift(int id) {
	lazy[lc] += lazy[id];
	lazy[rc] += lazy[id];
	seg[lc] += lazy[id];
	seg[rc] += lazy[id];

	lazy[id] = 0;
}
void upd(int ql , int qr , ll val , int l = 0 , int r = n , int id = 1) {
	if(r <= ql || qr <= l)
		return;
	if(ql <= l && r <= qr) {
		lazy[id] += val;
		seg[id] += val;
		return;
	}
	shift(id);

	int mid = r + l >> 1;
	upd(ql , qr , val , l , mid , lc);
	upd(ql , qr , val , mid , r , rc);

	seg[id] = max(seg[lc] , seg[rc]);
}
ll get(int ql , int qr , int l = 0 , int r = n , int id = 1) {
	if(r <= ql || qr <= l)
		return 0;
	if(ql <= l && r <= qr)
		return seg[id];
	shift(id);

	int mid = r + l >> 1;
	return max(get(ql , qr , l , mid , lc) , get(ql , qr , mid , r , rc));
}
int t;
void dfs(int u , int p = 0) {
	col[u] = (p == 1 ? u : col[p]);
	st[u] = t ++;

	for(auto [v , id] : adj[u]) {
		if(v == p)
			continue;
		
		h[v] = h[u] + w[id];
		ch[id] = v;

		dfs(v , u);
	}
	fn[u] = t;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> q >> mx;
	for(int i = 0 ; i < n-1 ; i ++) {
		ll u , v , W;
		cin >> u >> v >> W;

		adj[u].pb({v , i});
		adj[v].pb({u , i});
		w[i] = W;
	}
	dfs(1);

	for(int i = 1 ; i <= n ; i ++)
		upd(st[i] , st[i]+1 , h[i]);

	for(int i = 1 ; i <= n ; i ++) {
		if(col[i] != i)
			continue;
		
		seti.insert(-get(st[i] , fn[i]));
	}

	ll last = 0;
	while(q --) {
		ll d , e;
		cin >> d >> e;
		d = (d + last) % (n-1);
		e = (e + last) % mx;
		
		int u = ch[d];
		int v = col[u];

		seti.erase(seti.find(-get(st[v] , fn[v])));

		upd(st[u] , fn[u] , e - w[d]);

		seti.insert(-get(st[v] , fn[v]));

		w[d] = e;

		int cnt = 0;
		ll ans = 0;
		for(auto h : seti) {
			if(cnt == 2)
				break;
			ans += -1 * h;
			cnt ++;
		}
		cout << ans << endl;
		last = ans;
	}

	return 0;
}

Compilation message

diameter.cpp: In function 'void upd(int, int, ll, int, int, int)':
diameter.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = r + l >> 1;
      |            ~~^~~
diameter.cpp: In function 'll get(int, int, int, int, int)':
diameter.cpp:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int mid = r + l >> 1;
      |            ~~^~~
diameter.cpp: In function 'void dfs(int, int)':
diameter.cpp:85:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |  for(auto [v , id] : adj[u]) {
      |           ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5720 KB Output is correct
4 Correct 12 ms 5976 KB Output is correct
5 Correct 43 ms 6212 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 3 ms 5724 KB Output is correct
10 Correct 14 ms 6024 KB Output is correct
11 Correct 70 ms 6376 KB Output is correct
12 Correct 5 ms 8540 KB Output is correct
13 Correct 5 ms 8540 KB Output is correct
14 Correct 7 ms 8540 KB Output is correct
15 Correct 21 ms 8692 KB Output is correct
16 Correct 87 ms 8944 KB Output is correct
17 Correct 92 ms 19560 KB Output is correct
18 Correct 94 ms 19676 KB Output is correct
19 Correct 96 ms 19728 KB Output is correct
20 Correct 111 ms 19660 KB Output is correct
21 Correct 272 ms 20136 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 16212 KB Output is correct
2 Correct 189 ms 16136 KB Output is correct
3 Correct 174 ms 16212 KB Output is correct
4 Correct 176 ms 16464 KB Output is correct
5 Correct 160 ms 16608 KB Output is correct
6 Correct 221 ms 18632 KB Output is correct
7 Correct 151 ms 18340 KB Output is correct
8 Correct 185 ms 18516 KB Output is correct
9 Correct 176 ms 18964 KB Output is correct
10 Correct 168 ms 18516 KB Output is correct
11 Correct 189 ms 18936 KB Output is correct
12 Correct 204 ms 20320 KB Output is correct
13 Correct 157 ms 22004 KB Output is correct
14 Correct 182 ms 21896 KB Output is correct
15 Correct 194 ms 21768 KB Output is correct
16 Correct 173 ms 21840 KB Output is correct
17 Correct 186 ms 21848 KB Output is correct
18 Correct 221 ms 21612 KB Output is correct
19 Correct 139 ms 21840 KB Output is correct
20 Correct 147 ms 21952 KB Output is correct
21 Correct 207 ms 21980 KB Output is correct
22 Correct 185 ms 21920 KB Output is correct
23 Correct 196 ms 21712 KB Output is correct
24 Correct 199 ms 21612 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -