Submission #93755

#	Time	Username	Problem	Language	Result	Execution time	Memory
93755		psmao	Construction of Highway (JOI18_construction)	C++14	100 / 100	383 ms	86048 KiB

construction

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 100050;

int n, pa[maxn], a[maxn], U[maxn], V[maxn], bit[maxn], tim[maxn], T;
int cnt, disc[maxn], sz[maxn], top[maxn], dep[maxn];
VI adj[maxn];
vector<pii> V2;
stack<pii> St[maxn];

void dfs(int u, int fa = 0)
{
	sz[u] = 1;
	for(auto p : adj[u]) if(p != fa)
	{
		pa[p] = u;
		dfs(p, u);
		sz[u] += sz[p];
	}
}
void rdfs(int u, int fa, int chain)
{
	top[u] = chain;
	int mx = -1;
	for(auto p : adj[u])
		if(p != fa && (mx == -1 || sz[mx] < sz[p])) mx = p;
	if(mx != -1) {dep[mx] = dep[u] + 1; rdfs(mx, u, chain);}
	for(auto p : adj[u]) 
		if(p != fa && p != mx) {dep[p] = 0; rdfs(p, u, p);}
}
void add(int p, int w)
{
	for(int i = p; i <= cnt; i += i&(-i))
		if(tim[i] != T) {tim[i] = T; bit[i] = w;}
		else bit[i] += w;
}
int ask(int p, int ret = 0)
{
	for(int i = p; i > 0; i -= i&(-i))
		if(tim[i] == T) ret += bit[i];
	return ret;
}
ll calc()
{
	cnt = 0;
	fo(i,0,SZ(V2)-1) disc[++cnt] = V2[i].fi;
	sort(disc+1,disc+cnt+1);
	cnt = unique(disc+1,disc+cnt+1)-(disc+1);
	++ T; ll ret = 0;
	fo(i,0,SZ(V2)-1)
	{
		V2[i].fi = lower_bound(disc+1,disc+cnt+1,V2[i].fi)-(disc);
		ret += 1ll * ask(V2[i].fi-1) * V2[i].se;
		add(V2[i].fi, V2[i].se);
	}
	return ret;
}
int main()
{
	#ifdef MPS
		fp("1.in","r",stdin);
		fp("1.out","w",stdout);
	#endif
	sf("%d",&n);
	fo(i,1,n) sf("%d",&a[i]);
	fo(i,2,n) {sf("%d%d",&U[i],&V[i]); adj[U[i]].pb(V[i]); adj[V[i]].pb(U[i]);}
	dfs(1);
	rdfs(1, 0, 1);
	fo(i,2,n)
	{
		int p = V[i], val = a[V[i]], pos;
		V2.clear();
		while(p)
		{
			pos = dep[p]+1;
			p = top[p]; int t = 0;
			vector<pii> tmp;
			while(!St[p].empty() && St[p].top().se <= pos)
			{
				pii h = St[p].top(); St[p].pop();
				tmp.pb(mp(h.fi, h.se-t));
				t = h.se;
			}
			if(!St[p].empty()) tmp.pb(mp(St[p].top().fi, pos-t));
			St[p].push(mp(val, pos));
			fd(i,SZ(tmp)-1,0) V2.pb(tmp[i]);
			p = pa[p];
		}
		pf("%lld\n",calc());
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:94:4: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  sf("%d",&n);
    ^
construction.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fo(i,1,n) sf("%d",&a[i]);
              ^
construction.cpp:96:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fo(i,2,n) {sf("%d%d",&U[i],&V[i]); adj[U[i]].pb(V[i]); adj[V[i]].pb(U[i]);}
               ^

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