oj.uz

Submission #1020614

# Submission time Handle Problem Language Result Execution time Memory
1020614 2024-07-12T07:35:42 Z toan2602 Tree Rotations (POI11_rot) C++14
100 / 100
 284 ms 45960 KB 
#include<bits/stdc++.h>
 
using namespace std;
#define int long long
int n, x, idx = 1, a[1000005], bit[1000005], subtree[1000005];
vector<int> adj[1000005];
int RES = 0;
void add(int pos, int val) {
	while(pos <= idx) {
		bit[pos] += val;
		pos += pos & -pos;
	}
}
 
int get(int x) {
	if(x <= 0) return 0;
	int res = 0;
	for (; x; x-=x&(-x)) res+=bit[x];
	return res;
}
int range(int l, int r) {return get(r) - get(l-1);}
void build_sub(int u, int par) {
	subtree[u] = 1;
	for (int node: adj[u]) {
		if(node == par) continue;
		build_sub(node, u);
		subtree[u] += subtree[node];
	}
}
void build(int u) {
	cin >> x;
	if(x == 0) {
		int l, r;
		l = idx+1, r = idx+2;
		idx+=2;
		adj[u].push_back(l);
		adj[u].push_back(r);
		build(l);
		build(r);
	}
	else if(adj[u].size() == 0) a[u] = x;
}
 
pair<int,int> dfs2(int u) {
	pair<int, int> res = {range(a[u]+1,idx), range(1,a[u]-1)};
	if(a[u] == 0) res = {0,0};
	for (int node: adj[u]) {pair<int, int> val = dfs2(node); res.first+=val.first,res.second+=val.second;}
	return res;
}
 
void upd(int u, int tp) {
	if(adj[u].empty()) add(a[u], tp);
	for (int node: adj[u]) upd(node,tp);
}
 
void dfs(int u) {
	int mx = 0, p = -1, idx;
	for (int i = 0; i < adj[u].size(); i++) {
		int node = adj[u][i];
		if(mx < subtree[node]) mx = subtree[node], p = node, idx = i;
	}
	if(p == -1) {
		add(a[u],1);
		return;
	}
	if(idx == 1) swap(adj[u][0], adj[u][1]);
	dfs(adj[u][1]);
	upd(adj[u][1], -1);
	dfs(p);
	pair<int, int> val = dfs2(adj[u][1]);
	RES += min(val.first, val.second);
	upd(adj[u][1], 1);
}
void solve() {
	cin >> n;
 	build(1);
	n = idx;
	build_sub(1,-1);
	dfs(1);
	cout << RES;
}
 
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen("input.inp","r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}
}

Compilation message

rot.cpp: In function 'void dfs(long long int)':
rot.cpp:58:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < adj[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
rot.cpp: In function 'int main()':
rot.cpp:86:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
rot.cpp:87:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   freopen("output.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 11 ms 23900 KB Output is correct
3 Correct 15 ms 23936 KB Output is correct
4 Correct 13 ms 24060 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24328 KB Output is correct
2 Correct 13 ms 24312 KB Output is correct
3 Correct 13 ms 24412 KB Output is correct
4 Correct 12 ms 24412 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25436 KB Output is correct
2 Correct 19 ms 24920 KB Output is correct
3 Correct 35 ms 26264 KB Output is correct
4 Correct 19 ms 25204 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 27944 KB Output is correct
2 Correct 37 ms 28764 KB Output is correct
3 Correct 45 ms 30036 KB Output is correct
4 Correct 40 ms 30156 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35152 KB Output is correct
2 Correct 46 ms 33108 KB Output is correct
3 Correct 62 ms 31580 KB Output is correct
4 Correct 48 ms 31060 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 33496 KB Output is correct
2 Correct 57 ms 34388 KB Output is correct
3 Correct 64 ms 36944 KB Output is correct
4 Correct 59 ms 36708 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 40020 KB Output is correct
2 Correct 118 ms 38740 KB Output is correct
3 Correct 98 ms 39080 KB Output is correct
4 Correct 126 ms 38484 KB Output is correct
5 Correct 226 ms 37148 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 39772 KB Output is correct
2 Correct 117 ms 44372 KB Output is correct
3 Correct 135 ms 42840 KB Output is correct
4 Correct 98 ms 45212 KB Output is correct
5 Correct 284 ms 39228 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 40492 KB Output is correct
2 Correct 101 ms 41236 KB Output is correct
3 Correct 179 ms 39760 KB Output is correct
4 Correct 140 ms 40272 KB Output is correct
5 Correct 101 ms 45960 KB Output is correct
6 Correct 280 ms 39572 KB Output is correct