oj.uz

Submission #108626

# Submission time Handle Problem Language Result Execution time Memory
108626 2019-04-30T12:01:40 Z bharat2002 Tree Rotations (POI11_rot) C++14
63 / 100
 568 ms 47784 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=2e5 + 100;
#define int long long
int nxt, n, tree[4*N], arr[2*N], ssum[N], ans[N];vector<int> vals[2*N], adjlist[2*N];
void input(int i)
{
	int v;cin>>v;
	if(v==0)
	{
		adjlist[i].push_back(nxt);input(nxt++);adjlist[i].push_back(nxt);input(nxt++);
		ssum[i]=ssum[adjlist[i][0]] + ssum[adjlist[i][1]];
		if(ssum[adjlist[i][0]]>ssum[adjlist[i][1]]) swap(adjlist[i][0], adjlist[i][1]);
	}
	else
	{
		arr[i]=v;ssum[i]=1;return;
	}
}
int valind;
void remove(int i=1, int l=1, int r=n){
	if(tree[i]==0) return;
	if(l==r)
	{
		tree[i]=0;
		vals[valind].push_back(l);
		//cout<<valind<<" "<<l<<endl;
		return;
	}
	int mid=(l+r)>>1;remove(2*i, l, mid);remove(2*i+1, mid+1, r);tree[i]=0;
}
void update(int ql, int qr, int i=1, int l=1, int r=n)
{
	if(l>qr||r<ql) return;
	if(l==r)
	{
		tree[i]=1;return;
	}
	int mid=(l+r)>>1;update(ql, qr, 2*i, l, mid);update(ql, qr, 2*i+1, mid+1, r);
	tree[i]=tree[2*i] + tree[2*i+1];
}
int query(int ql, int qr, int i=1, int l=1, int r=n)
{
	if(l>qr||r<ql) return 0;
	if(l>=ql&&r<=qr) return tree[i];
	int mid=(l+r)>>1;return query(ql, qr, 2*i, l, mid) + query(ql, qr, 2*i+1, mid+1, r);
}
void dfs(int i)
{
	if(adjlist[i].empty())
	{
		ans[i]=0;update(arr[i], arr[i]);return;
	}
	dfs(adjlist[i][0]);valind=adjlist[i][0];remove();
	dfs(adjlist[i][1]);int tans=0;
	for(auto j:vals[adjlist[i][0]])
	{
		tans+=query(1, j-1);
	}
	for(auto j:vals[adjlist[i][0]])
	{
		update(j, j);
	}
	ans[i]=min(tans, ssum[adjlist[i][0]]*ssum[adjlist[i][1]] - tans) + ans[adjlist[i][0]] + ans[adjlist[i][1]];
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n;nxt=2;
	input(1);


	dfs(1);
/*	for(int i=1;i<=5;i++)
	{
		cout<<i<<": "<<ans[i]<<endl;
	}*/

	cout<<ans[1];
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19200 KB Output is correct
2 Correct 21 ms 19200 KB Output is correct
3 Correct 21 ms 19200 KB Output is correct
4 Correct 21 ms 19192 KB Output is correct
5 Correct 20 ms 19200 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19200 KB Output is correct
2 Correct 22 ms 19200 KB Output is correct
3 Correct 20 ms 19200 KB Output is correct
4 Correct 21 ms 19328 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19320 KB Output is correct
2 Correct 21 ms 19328 KB Output is correct
3 Correct 21 ms 19348 KB Output is correct
4 Correct 20 ms 19328 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19840 KB Output is correct
2 Correct 29 ms 19968 KB Output is correct
3 Correct 25 ms 19968 KB Output is correct
4 Correct 23 ms 20132 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 21220 KB Output is correct
2 Correct 52 ms 21328 KB Output is correct
3 Correct 146 ms 24952 KB Output is correct
4 Correct 46 ms 21496 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 28404 KB Output is correct
2 Correct 132 ms 27768 KB Output is correct
3 Correct 135 ms 29024 KB Output is correct
4 Correct 133 ms 29260 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 34480 KB Output is correct
2 Correct 209 ms 34000 KB Output is correct
3 Correct 240 ms 34040 KB Output is correct
4 Correct 174 ms 32760 KB Output is correct

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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