Submission #85945

#	Time	Username	Problem	Language	Result	Execution time	Memory
85945		bash	Construction of Highway (JOI18_construction)	C++17	100 / 100	598 ms	187804 KiB

construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
int a[111111];
int sz[111111];
int in[111111];
int rin[111111];
int t;
int out[111111];
deque<ii> chain[111111]; //heavy chain starting at vertex u
int nxt[111111];
vi adj[111111];
int par[111111];
int h[111111];
 
void addtochain(int u, int v)
{
	if(chain[u].empty()) chain[u].pb(mp(1,v));
	else if(chain[u].back().fi==v) chain[u].back().se++;
	else chain[u].pb(mp(v,1));
}
 
void dfs_sz(int v = 0)
{
    sz[v] = 1;
    for(auto &u: adj[v])
    {
		par[u] = v; h[u] = h[v] + 1;
        dfs_sz(u);
        sz[v] += sz[u];
        if(sz[u] > sz[adj[v][0]])
            swap(u, adj[v][0]);
    }
}
 
void dfs_hld(int v = 0)
{
    in[v] = t++;
    rin[in[v]] = v;
    for(auto u: adj[v])
    {
        nxt[u] = (u == adj[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
    out[v] = t;
}
 
int fen[111111];
int N;
 
void init(int n)
{
	N=n;
	for(int i=0;i<=N;i++) fen[i]=0;
}
 
void update(int pos, int v)
{
	pos++;
	for(;pos<=N;pos+=(pos&(-pos)))
	{
		fen[pos]+=v;
	}
}
 
int query(int pos)
{
	pos++;
	int sum=0;
	for(;pos;pos-=(pos&(-pos)))
	{
		sum+=fen[pos];
	}
	return sum;
}
 
ll calc_path(int u)
{
	vector<ii> V; vi coord;
	while(u!=-1)
	{
		int nu = nxt[u];
		int siz = h[u] - h[nu] + 1;
		vector<ii> tst;
		//cerr<<"CHAIN : "<<u<<' '<<nu<<'\n';
		for(int i=0;i<chain[nu].size();i++)
		{
			int cnt = chain[nu][i].fi; int v = chain[nu][i].se;
			if(cnt<=siz)
			{
				tst.pb(mp(cnt,v));
				siz-=cnt;
			}
			else
			{
				tst.pb(mp(siz,v));
				break;
			}
		}
		for(int i=int(tst.size())-1;i>=0;i--) 
		{
			V.pb(tst[i]); coord.pb(tst[i].se);
		}
		u=par[nu];
	}
	reverse(V.begin(),V.end());
	sort(coord.begin(),coord.end()); coord.erase(unique(coord.begin(),coord.end()),coord.end());
	//cerr<<coord.size()<<'\n';
	init(int(coord.size()));
	ll ans = 0; ll tot = 0;
	for(ii x:V)
	{
		x.se = lower_bound(coord.begin(),coord.end(),x.se)-coord.begin();
		ans += x.fi*(tot - query(x.se));
		//cerr<<x.fi<<' '<<x.se<<'\n';
		tot+=x.fi;
		update(x.se, x.fi);
	}
	//cerr<<'\n';
	return ans;
}
 
void addedge(int u, int v)
{
	while(u!=-1)
	{
		int nu = nxt[u];
		int siz = h[u] - h[nu] + 1;
		while(chain[nu].size()>0)
		{
			int cnt = chain[nu][0].fi;
			if(cnt<=siz)
			{
				chain[nu].pop_front();
				siz-=cnt;
			}
			else
			{
				chain[nu].front().fi -= siz;
				break;
			}
		}
		chain[nu].push_front(mp(h[u]-h[nu]+1, v));
		u=par[nu];
	}
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	nxt[0] = 0; addtochain(0,a[0]);
	vector<ii> edges;
	par[0]=-1;
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); edges.pb(mp(u,v));
	}
	dfs_sz(); dfs_hld();
	for(int i=0;i<n-1;i++)
	{
		cout<<calc_path(edges[i].fi)<<'\n';
		addedge(edges[i].se, a[edges[i].se]);
		//calc_path(edges[i].fi, edges[i].se);
	}
}

Compilation message (stderr)

construction.cpp: In function 'll calc_path(int)':
construction.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<chain[nu].size();i++)
               ~^~~~~~~~~~~~~~~~~

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