Submission #309307

#	Time	Username	Problem	Language	Result	Execution time	Memory
309307		arnold518	Construction of Highway (JOI18_construction)	C++14	100 / 100	1923 ms	19052 KiB

construction

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N;
vector<int> adj[MAXN+10];
int A[MAXN+10], B[MAXN+10];

int par[MAXN+10], sz[MAXN+10];

void dfs(int now)
{
	sz[now]=1;
	for(int nxt : adj[now])
	{
		dfs(nxt);
		sz[now]+=sz[nxt];
	}
}

int head[MAXN+10], dfn[MAXN+10], idfn[MAXN+10], cnt;

void hld(int now)
{
	dfn[now]=++cnt;
	idfn[dfn[now]]=now;

	int heavy=0;
	for(int nxt : adj[now])
	{
		if(sz[heavy]<sz[nxt]) heavy=nxt;
	}
	if(heavy==0) return;

	head[heavy]=head[now];
	hld(heavy);

	for(int nxt : adj[now])
	{
		if(nxt==heavy) continue;
		head[nxt]=nxt;
		hld(nxt);
	}
}

struct Data
{
	int l, r, v;
};
vector<Data> V[MAXN+10];

vector<int> comp;

struct BIT
{
	int tree[MAXN+10];
	void init() { memset(tree, 0, sizeof(tree)); }
	void update(int i, int x) { for(; i<=N; i+=(i&-i)) tree[i]+=x; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for(int i=1; i<=N; i++) A[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;

	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		par[v]=u;
		B[i]=v;
	}

	dfs(1);
	head[1]=1;
	hld(1);

	//printf("DFN\n");
	//for(int i=1; i<=N; i++) printf("%d ", dfn[i]); printf("\n");

	V[1].push_back({1, 1, A[1]});
	for(int i=1; i<N; i++)
	{
		int u=par[B[i]], v=B[i];

		int now=v;
		vector<pii> V2;
		while(1)
		{
			vector<pii> VV;
			while(!V[head[now]].empty() && V[head[now]].back().r<=dfn[now])
			{
				VV.push_back({V[head[now]].back().v, V[head[now]].back().r-V[head[now]].back().l+1});
				V[head[now]].pop_back();
			}
			if(!V[head[now]].empty() && V[head[now]].back().l<=dfn[now])
			{
				VV.push_back({V[head[now]].back().v, dfn[now]-V[head[now]].back().l+1});
				V[head[now]].back().l=dfn[now]+1;
			}
			V[head[now]].push_back({dfn[head[now]], dfn[now], A[v]});
			reverse(VV.begin(), VV.end());
			for(auto it : VV) V2.push_back(it);

			if(head[now]==1) break;
			now=par[head[now]];
		}

		reverse(V2.begin(), V2.end());
		bit.init();

		ll ans=0;
		//printf("V2 of %d %d is\n", u, v);
		for(auto it : V2)
		{
			//printf("%d %d\n", it.first, it.second);
			ans+=(ll)it.second*(bit.query(N)-bit.query(it.first));
			bit.update(it.first, it.second);
		}
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:95:7: warning: unused variable 'u' [-Wunused-variable]
   95 |   int u=par[B[i]], v=B[i];
      |       ^
construction.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
construction.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
construction.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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