oj.uz

답안 #108543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
108543 2019-04-30T07:04:06 Z bharat2002 Tree Rotations (POI11_rot) C++14
0 / 100
 327 ms 49284 KB 
/*input
8
0
0
0
8
7
0
6
5
0
0
4
3
0
2
1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
vector<int> adjlist[2*N];int arr[2*N], n;
int pos[2*N], ans[2*N];//vals[pos[i]] gives the set of values for the ith node. 
int cval, nxt;
int tree[4*N];int ssum[2*N];
vector<int> vals[2*N];
void build(int i=1, int l=1, int r=n)
{
	tree[i]=0;
	if(l==r) return;
	int mid=(l+r)>>1;build(2*i, l, mid);build(2*i+1, mid+1, r);
}
int curpos;
void remove(int i=1, int l=1, int r=n)
{
	if(tree[i]==0) return;
	if(l==r)
	{
		
		vals[curpos].push_back(l);tree[i]=0;return;
	}
	tree[i]=0;int mid=(l+r)>>1;remove(2*i, l, mid);remove(2*i+1, mid+1, r);
}
int ql, qr;
void update(int i=1, int l=1, int r=n)
{
	if(l>qr||r<ql) return;
	if(l>=ql&&r<=qr)
	{
		tree[i]=1;return;
	}
	int mid=(l+r)>>1;update(2*i, l, mid);update(2*i+1, mid+1, r);
	tree[i]=tree[2*i] + tree[2*i+1];
}
int query(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(2*i, l, mid) + query(2*i+1, mid+1, r);
}
void dfs(int i)
{
	int v;cin>>v;
	if(v==0)
	{
		adjlist[i].push_back(cval);
		dfs(cval++);
		adjlist[i].push_back(cval);dfs(cval++);ssum[i]=ssum[adjlist[i][1]]+ssum[adjlist[i][0]];
		if(ssum[adjlist[i][0]]>ssum[adjlist[i][1]]) swap(adjlist[i][0], adjlist[i][1]);
	}
	else
	{
		arr[i]=v;ssum[i]=1;
		pos[i]=nxt++;
		return;
	}
}
void mdfs(int i)
{
	if(adjlist[i].empty())
	{
		ans[i]=0;ql=qr=arr[i];update();
		return;
	}
	mdfs(adjlist[i][0]);curpos=adjlist[i][0];
	remove();
	mdfs(adjlist[i][1]);ql=1;qr=n;
	int prevsum=query();int tot=0, prevpos=n;
	reverse(vals[curpos].begin(), vals[curpos].end());
	for(auto j:vals[curpos])
	{
		ql=1;qr=j-1;tot+=query();
	}
	
	if(i==2)
	{
		cout<<curpos<<": ";
		for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
	}
	for(auto j:vals[curpos])
	{
		ql=qr=j;update();
	}
	if(i==2)
	{
		cout<<tree[1]<<endl;
	}
	ans[i]=ans[adjlist[i][0]] + ans[adjlist[i][1]] + min(tot, ssum[adjlist[i][0]]*ssum[adjlist[i][1]] - tot);
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n;cval=2;nxt=1;
	dfs(1);
	mdfs(1);
/*	for(int i=1;i<=15;i++) {cout<<i<<": ";//<<ans[i]<<endl;
		for(auto j:vals[i]) cout<<j<<" ";cout<<endl;
//		cout<<" val="<<arr[i]<<endl;
	}*/
	cout<<ans[1];
}

Compilation message

rot.cpp: In function 'void mdfs(long long int)':
rot.cpp:105:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
   ^~~
rot.cpp:105:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
                                         ^~~~
rot.cpp:95:6: warning: unused variable 'prevsum' [-Wunused-variable]
  int prevsum=query();int tot=0, prevpos=n;
      ^~~~~~~
rot.cpp:95:33: warning: unused variable 'prevpos' [-Wunused-variable]
  int prevsum=query();int tot=0, prevpos=n;
                                 ^~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 19200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 19192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 19328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 19840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 21376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 26872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 136 ms 35512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 182 ms 36880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 303 ms 47260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 307 ms 48228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 327 ms 49284 KB Output isn't correct
2 Halted 0 ms 0 KB -