Submission #1082518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082518		vjudge1	Construction of Highway (JOI18_construction)	C++17	16 / 100	2021 ms	2804 KiB

construction

#include<bits/stdc++.h>
#define INF 1e18
#define fi first
#define se second
#define FOR(i, k, n) for(ll i = k; i <= n; i++)
#define FOR1(i, k, n) for(ll i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "BAI1.inp"
#define output "BAI1.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int base = 31;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
int par[maxn];
int a[maxn], bit[maxn];
int t;
void update(int x)
{
	while(x <= t)
	{
		bit[x]++;
		x += x & -x;
	}
}
int get(int x)
{
	int ans = 0;
	while(x > 0)
	{
		ans += bit[x];
		x -= x & -x;
	}
	return ans;
}
int main()
{
	fastio;
	int n;
	cin >> n;
	FOR(i, 1, n)
		cin >> a[i];
	vii vvv;
	FOR(i, 1, n)
		vvv.pb({a[i], i});
	sort(vvv.begin(), vvv.end());
	int truoc = -1;
	for(auto x : vvv)
	{
		if(x.fi > truoc)
			t++;
		a[x.se] = t;
		truoc = x.fi;
	}
	FOR(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		vi vv;
		par[v] = u;
		while(u != 1)
		{
			vv.pb(u);
			u = par[u];
		}
		vv.pb(1);
		if(vv.size() == 1)
			cout << "0\n";
		else
		{
			int ans = 0;
			FOR(i, 1, n)
				bit[i] = 0;
			for(auto x : vv)
			{
				ans += get(a[x] - 1);
				update(a[x]);
			}
			cout << ans << "\n";
		}
		for(auto x : vv)
			a[x] = a[v];
	}
	re;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84