Submission #1098608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098608	2024-10-09T16:08:09 Z	flyingkite	Tree Rotations (POI11_rot)	C++17	100 / 100	224 ms	48848 KB

//#pragma GCC optimize("O3","unroll-loops")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
 
const long long inf = 1e18+1;
const int mod = 1e9+7;
const int MAXN = 1e6+100;
 
#define int long long
 
int bit[MAXN] , n;
void upd(int x , int val){
	while(x <= n){
		bit[x] += val;
		x += (x & (-x));
	}
}
int get(int x){
	int res = 0;
	while(x > 0){
		res += bit[x];
		x -= (x & (-x));
	}
	return res;
}
 
vector<int> adj[MAXN];
int id = 1 , c[MAXN] , sz[MAXN];
void Input(){
	int x; cin >> x;
	c[id] = x;
	if(x!=0) return;
	int t = id;
	adj[t].push_back(id+1);
	id++ ; Input();
	adj[t].push_back(id+1);
	id++ ; Input();
}
 
void dfs_sz(int u){
	sz[u] = 1;
	for(auto v : adj[u]) dfs_sz(v) , sz[u] += sz[v];
}
void modify(int u , int val){
	if(adj[u].size() == 0){
		upd(c[u] , val); return;
	}
	for(auto v : adj[u]) modify(v , val);
}
int cnt1 = 0 , cnt2 = 0;
void cal(int u){
	if(adj[u].size() == 0){
		cnt1 += get(c[u] - 1);
		cnt2 += get(n) - get(c[u]);
		return;
	}
	for(auto v : adj[u]) cal(v);
}
int ans[MAXN];
void dfs(int u){
	if(adj[u].size() == 0){
		upd(c[u] , 1); return;
	}
	int bc = (sz[adj[u][0]] > sz[adj[u][1]] ? 0 : 1);
	int sc = bc ^ 1;
	bc = adj[u][bc]; sc = adj[u][sc];
	dfs(sc);
	modify(sc , -1);
	dfs(bc);
	cnt1 = cnt2 = 0;
	cal(sc);
	modify(sc , 1);
	ans[u] = ans[bc] + ans[sc] + min(cnt1 , cnt2);
}
int32_t main(){
  	//freopen("TRAVEL.INP", "r", stdin);
	//freopen("Nowruz.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	Input();
	dfs_sz(1);
	dfs(1);
	cout << ans[1] << "\n";
 
	return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	23900 KB	Output is correct
2	Correct	10 ms	23900 KB	Output is correct
3	Correct	9 ms	23868 KB	Output is correct
4	Correct	9 ms	23900 KB	Output is correct
5	Correct	9 ms	23900 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	23900 KB	Output is correct
2	Correct	10 ms	23948 KB	Output is correct
3	Correct	9 ms	23964 KB	Output is correct
4	Correct	9 ms	23900 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23900 KB	Output is correct
2	Correct	11 ms	23900 KB	Output is correct
3	Correct	11 ms	23900 KB	Output is correct
4	Correct	11 ms	23900 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	24412 KB	Output is correct
2	Correct	12 ms	24144 KB	Output is correct
3	Correct	14 ms	24548 KB	Output is correct
4	Correct	13 ms	24588 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	25436 KB	Output is correct
2	Correct	19 ms	25056 KB	Output is correct
3	Correct	31 ms	26716 KB	Output is correct
4	Correct	15 ms	25436 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	28716 KB	Output is correct
2	Correct	32 ms	29520 KB	Output is correct
3	Correct	34 ms	30872 KB	Output is correct
4	Correct	34 ms	31048 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	36184 KB	Output is correct
2	Correct	45 ms	34436 KB	Output is correct
3	Correct	52 ms	32956 KB	Output is correct
4	Correct	43 ms	32336 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	35156 KB	Output is correct
2	Correct	55 ms	36064 KB	Output is correct
3	Correct	54 ms	38644 KB	Output is correct
4	Correct	53 ms	38324 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	42580 KB	Output is correct
2	Correct	100 ms	41552 KB	Output is correct
3	Correct	90 ms	41300 KB	Output is correct
4	Correct	105 ms	40892 KB	Output is correct
5	Correct	160 ms	39764 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	42324 KB	Output is correct
2	Correct	102 ms	47196 KB	Output is correct
3	Correct	109 ms	45648 KB	Output is correct
4	Correct	100 ms	47952 KB	Output is correct
5	Correct	224 ms	42064 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	132 ms	42836 KB	Output is correct
2	Correct	98 ms	44368 KB	Output is correct
3	Correct	164 ms	42872 KB	Output is correct
4	Correct	128 ms	43088 KB	Output is correct
5	Correct	95 ms	48848 KB	Output is correct
6	Correct	210 ms	42576 KB	Output is correct

Submission #1098608

Compilation message