Submission #1015641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015641		pan	Construction of Highway (JOI18_construction)	C++17	100 / 100	240 ms	93564 KiB

construction

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
 
ll n, hld_label = 0;
ll const MAXN = 100010;
vector<ll> adj[MAXN];
ll depth[MAXN], siz[MAXN], heavyp[MAXN], parent[MAXN], in[MAXN], out[MAXN], val[MAXN], a[MAXN], b[MAXN];
deque<pi> dq[MAXN];
void dfs_size(ll p, ll node) // hld pre-order + subtree size
{
	if (adj[node].size()>=2 && adj[node][0]==p) swap(adj[node][0], adj[node][1]);
	siz[node]=1;
	for (auto& u: adj[node])
	{
		if (u==p) continue;
		depth[u] = depth[node]+1;
		parent[u] = node;
		dfs_size(node, u);
		siz[node] += siz[u];
		if (siz[u]>siz[adj[node][0]]) swap(adj[node][0], u); // order heavy edge together
	}
}
// heavyp = next ancester with conseutive path (as in sgtree) to current node
void dfs_hld(ll p, ll node) 
{
	hld_label++;
	in[node] = hld_label;
	dq[heavyp[node]].pb(mp(val[node], 1));
	for (ll u: adj[node])
	{
		if (u==p) continue;
		if (u==adj[node][0]) heavyp[u] = heavyp[node]; // trace the topmost vertice in the path
		else heavyp[u] = u; // for light vertice, this is simply itself
		dfs_hld(node, u);
	}
	out[node] = hld_label;
		
	
}
 
 
// BIT
vector<ll> dis;
vector<ll> fenwick(MAXN,0);
 
ll ps(ll i)
{
	if (i==0) return 0;
	ll sum=0;
	while (i>0)
	{
		sum+=fenwick[i];
		i-=i&(-i);
	}
	return sum;
}
void update(ll i, ll v)
{
	while (i<=100005)
	{
		fenwick[i]+=v;
		i+=i&(-i);
	}
}
 
int main()
{
	input(n);
	for (ll i=1; i<=n; ++i) {input(val[i]); dis.pb(val[i]);}
	discretize(dis);
	for (ll i=1; i<=n; ++i)  {val[i] = lb(all(dis), val[i])-dis.begin() + 1;}
	for (ll i=1; i<=n-1; ++i)
	{
		input2(a[i], b[i]);
		adj[a[i]].pb(b[i]);
	}
	parent[1] = -1;
	depth[1] = 0;
	heavyp[1] = 1;
	dfs_size(-1, 1);
	dfs_hld(-1, 1);
	for (ll i=1; i<=n-1; ++i)
	{
		//show(i);
		ll ans = 0;
		ll now = a[i];
		vector<pi> undo;
		while (now!=-1) 
		{
			//show(now);
			vector<pi> qq;
			ll cnt = depth[now] - depth[heavyp[now]] +1;
			while (dq[heavyp[now]].size() && cnt)
			{
				ll take = min(dq[heavyp[now]].front().s, cnt);
				//show2(dq[heavyp[now]].front().f, dq[heavyp[now]].front().s);
				cnt-=take;
				dq[heavyp[now]].front().s-=take;
				ll idx = dq[heavyp[now]].front().f;
				//ans += ps(idx-1)*take;
				//update(idx, take);
				qq.pb(mp(idx, take));
				if (dq[heavyp[now]].front().s ==0) dq[heavyp[now]].pop_front();
			}
			dq[heavyp[now]].push_front(mp(val[b[i]], depth[now] - depth[heavyp[now]] +1));
			now = parent[heavyp[now]];
			reverse(all(qq));
			for (pi u: qq) ans += ps(u.f-1)*u.s, update(u.f, u.s), undo.pb(u);
		}
		for (pi u: undo) update(u.f, -u.s);
		
		print(ans, '\n');
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
construction.cpp:101:2: note: in expansion of macro 'input'
  101 |  input(n);
      |  ^~~~~
construction.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
construction.cpp:102:27: note: in expansion of macro 'input'
  102 |  for (ll i=1; i<=n; ++i) {input(val[i]); dis.pb(val[i]);}
      |                           ^~~~~
construction.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:107:3: note: in expansion of macro 'input2'
  107 |   input2(a[i], b[i]);
      |   ^~~~~~

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