oj.uz

Submission #521334

# Submission time Handle Problem Language Result Execution time Memory
521334 2022-02-01T18:30:51 Z Jasiekstrz Construction of Highway (JOI18_construction) C++17
0 / 100
 3 ms 2764 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int P=(1<<17);
int tab[N+10];
int que[N+10];
vector<int> e[N+10];
int par[N+10];
int dep[N+10];
int up[N+10];
int pre[N+10];
int post[N+10];
int pot;
pair<int,int> tr[2*P+10];
int fen[P+10];
void upd(int x,pair<int,int> c)
{
	for(x+=pot-1;x>=1;x/=2)
		tr[x]=max(tr[x],c);
	return;
}
pair<int,int> read(int l,int r)
{
	pair<int,int> ans={0,1};
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans=max(ans,tr[l++]);
		if(r%2==0)
			ans=max(ans,tr[r--]);
	}
	return ans;
}
void dfs_pre(int x)
{
	static int nr=0;
	pre[x]=++nr;
	dep[x]=dep[par[x]]+1;
	for(auto v:e[x])
		dfs_pre(v);
	post[x]=nr;
	return;
}
int g(int x)
{
	return read(pre[x],post[x]).se;
}
int lsb(int x)
{
	return x&(-x);
}
int read_inv(int x)
{
	int ans=0;
	for(;x>0;x-=lsb(x))
		ans+=fen[x];
	return ans;
}
void add_inv(int x,int c)
{
	for(;x<=pot;x+=lsb(x))
		fen[x]+=c;
	return;
}
long long solve_inv(vector<tuple<int,int,int>> &vec)
{
	sort(vec.begin(),vec.end());
	long long ans=0;
	for(auto [a,b,c]:vec)
	{
		ans+=(long long)c*read_inv(b-1);
		add_inv(b,c);
	}
	for(auto [a,b,c]:vec)
		add_inv(b,-c);
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>tab[i];
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		par[b]=a;
		que[i]=b;
	}
	dfs_pre(1);
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=2*pot;i++)
		tr[i]={0,1};
	for(int qi=1;qi<n;qi++)
	{
		vector<tuple<int,int,int>> vec;
		for(int x=par[que[qi]];x>0;)
		{
			int gr=g(x);
			//cerr<<qi<<" "<<x<<" "<<gr<<"\n";
			vec.push_back({tab[gr],vec.size()+1,dep[x]-dep[up[gr]]});
			swap(x,up[gr]);
		}
		cout<<solve_inv(vec)<<"\n";
		upd(pre[que[qi]],{qi,que[qi]});
		up[que[qi]]=0;
	}
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 2 ms 2712 KB Output is correct
8 Correct 2 ms 2672 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2680 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Incorrect 3 ms 2636 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 2 ms 2712 KB Output is correct
8 Correct 2 ms 2672 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2680 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Incorrect 3 ms 2636 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 2 ms 2712 KB Output is correct
8 Correct 2 ms 2672 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2680 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Incorrect 3 ms 2636 KB Output isn't correct
23 Halted 0 ms 0 KB -