oj.uz

Submission #30107

# Submission time Handle Problem Language Result Execution time Memory
30107 2017-07-22T06:21:47 Z 김동현(#1246) Tree Rotations (POI11_rot) C++14
100 / 100
 299 ms 12112 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, a[400010], lc[400010], rc[400010], s[400010], c = 1;
ll ans;

void g(int x){
	if(a[x]){
		s[x] = 1;
		return;
	}
	lc[x] = ++c; g(c);
	rc[x] = ++c; g(c);
	if(s[lc[x]] > s[rc[x]]) swap(lc[x], rc[x]);
	s[x] = s[lc[x]] + s[rc[x]];
}

struct BIT{
	int dat[200010];
	void upd(int x, int v){ for(; x <= n; x += x & -x) dat[x] += v; }
	int get(int x){ int ret = 0; for(; x; x -= x & -x) ret += dat[x]; return ret; }
} B;

void add(ll &cur, int x){
	if(a[x]){
		cur += B.get(a[x]);
		return;
	}
	add(cur, lc[x]);
	add(cur, rc[x]);
}

void upd(int x, int v){
	if(a[x]){
		B.upd(a[x], v);
		return;
	}
	upd(lc[x], v);
	upd(rc[x], v);
}

void f(int x){
	if(a[x]){
		B.upd(a[x], 1);
		return;
	}
	f(lc[x]);
	upd(lc[x], -1);
	f(rc[x]);
	ll cur = 0;
	add(cur, lc[x]);
	ans += min(cur, 1LL * s[lc[x]] * s[rc[x]] - cur);
	upd(lc[x], 1);
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < 2 * n; i++) scanf("%d", a + i);
	g(1);
	f(1);
	printf("%lld\n", ans);
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:58:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
rot.cpp:59:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i < 2 * n; i++) scanf("%d", a + i);
                                                   ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9052 KB Output is correct
2 Correct 0 ms 9052 KB Output is correct
3 Correct 0 ms 9052 KB Output is correct
4 Correct 0 ms 9052 KB Output is correct
5 Correct 0 ms 9052 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9052 KB Output is correct
2 Correct 0 ms 9052 KB Output is correct
3 Correct 0 ms 9052 KB Output is correct
4 Correct 0 ms 9052 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9052 KB Output is correct
2 Correct 0 ms 9052 KB Output is correct
3 Correct 0 ms 9052 KB Output is correct
4 Correct 0 ms 9052 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 0 ms 9052 KB Output is correct
3 Correct 0 ms 9052 KB Output is correct
4 Correct 0 ms 9052 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9268 KB Output is correct
2 Correct 6 ms 9052 KB Output is correct
3 Correct 39 ms 9052 KB Output is correct
4 Correct 6 ms 9156 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9052 KB Output is correct
2 Correct 29 ms 9552 KB Output is correct
3 Correct 33 ms 9976 KB Output is correct
4 Correct 26 ms 9904 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11400 KB Output is correct
2 Correct 33 ms 10304 KB Output is correct
3 Correct 53 ms 9604 KB Output is correct
4 Correct 46 ms 9144 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9052 KB Output is correct
2 Correct 49 ms 9584 KB Output is correct
3 Correct 43 ms 10840 KB Output is correct
4 Correct 36 ms 10748 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 10216 KB Output is correct
2 Correct 123 ms 9600 KB Output is correct
3 Correct 93 ms 9836 KB Output is correct
4 Correct 123 ms 9456 KB Output is correct
5 Correct 199 ms 9052 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 9492 KB Output is correct
2 Correct 96 ms 11680 KB Output is correct
3 Correct 126 ms 10844 KB Output is correct
4 Correct 96 ms 12112 KB Output is correct
5 Correct 266 ms 9052 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 9312 KB Output is correct
2 Correct 136 ms 9728 KB Output is correct
3 Correct 189 ms 9052 KB Output is correct
4 Correct 146 ms 9320 KB Output is correct
5 Correct 99 ms 12052 KB Output is correct
6 Correct 299 ms 9052 KB Output is correct