Submission #712402

#	Time	Username	Problem	Language	Result	Execution time	Memory
712402		Antekb	Construction of Highway (JOI18_construction)	C++17	16 / 100	2078 ms	26456 KiB

construction

#include<bits/stdc++.h>

#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
#define all(x) (x).begin(), (x).end()

using namespace std;

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t))cerr<<", ";
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=1e5+5;
vi E[N];
int pre[N], sz[N], par[N], sci[N], dep[N], val[N], co[N];
int wsk;
void dfs_sz(int v){
	for(int u:E[v]){
		if(u!=par[v]){
			par[u]=v;
			dep[u]=dep[v]+1;
			dfs_sz(u);
			sz[v]+=sz[u];
		}
	}
	sz[v]+=1;
	for(int &u:E[v])if(u==par[v])swap(u, E[v].back());
	if(v!=1)E[v].pp();
	for(int &u:E[v])if(sz[u]>sz[E[v][0]])swap(u, E[v][0]);
	//deb(v, E[v].size());
}
void dfs(int v){
	co[wsk]=v;
	pre[v]=wsk++;
	for(int u:E[v]){
		//deb(v, u);
		if(u==E[v][0])sci[wsk]=sci[pre[v]];
		else{
			sci[wsk]=wsk;
			//deb(v, wsk);
		}
		dfs(u);
	}
}
set<int> S[N];
ll calc(int v){
	vector<pair<int, int> > V;
	v=pre[v];
	int t=val[v];
	bool czy=1;
	while(true){
		int u=sci[v];
		//deb(v, u, S[u].size());
		if(S[u].size()){
			//deb(*S[u].begin());
		}
		vector<pair<int, int> > V2;
		int prv=u-1;
		while(prv<v-czy){
			//deb("a");
			//assert(S[u].size());
			int a=*S[u].begin();
			if(a>v-czy){
				V2.eb(v-czy-prv, val[a]);
			}
			else{
				V2.eb(a-prv, val[a]);
				S[u].erase(a);
			}
			prv=a;
		}
		reverse(all(V2));
		for(pii &i:V2)V.pb(i);
		S[u].insert(v);
		val[v]=t;
		if(u==0)break;
		v=pre[par[co[u]]];
		czy=0;
	}
	reverse(all(V));
	//deb(V.size());
	for(pii i:V){
		//deb(i.st, i.nd);
	}
	ll ans=0;
	for(int i=0; i<V.size(); i++){
		for(int j=0; j<i; j++){
			if(V[j].nd>V[i].nd)ans+=V[j].st*1ll*V[i].st;
		}
	}
	return ans;
}
int main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	vi V(n);
	for(int &i:V)cin>>i;
	vector<pii> edg(n-1);
	for(pii &i:edg)cin>>i.st>>i.nd, E[i.st].pb(i.nd), E[i.nd].pb(i.st);
	dfs_sz(1);
	dfs(1);
	for(int i=1; i<=n; i++){
		//deb(i, pre[i], par[i], val[i], sci[pre[i]], sz[i]);
	}
	S[0].insert(0);
	for(int i=1; i<=n; i++){
		val[pre[i]]=V[i-1];
	}
	for(pii i:edg){
		cout<<calc(i.nd)<<"\n";
	}
}

Compilation message (stderr)

construction.cpp: In function 'll calc(int)':
construction.cpp:97:10: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   97 |  for(pii i:V){
      |          ^
construction.cpp:101:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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