Submission #588658

#	Time	Username	Problem	Language	Result	Execution time	Memory
588658		angelo_torres	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	136 ms	15500 KiB

roadsideadverts

#include <bits/stdc++.h>
#define f(i,j,n) for(ll i = j; i < n; ++i)
#define fr(i,j,n) for(ll i = j; i >= n; --i)
#define ff first
#define ss second
#define sz(v) (int) v.size()


using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> ii;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long double ld;

const int N = 5e4 + 20;
const int M = 2e3 + 20;
const ll inf = 1e18;

int n,p[N][18],sm[N][18],in[N],out[N],tim = 0;
vii adj[N];


void dfs(int v,int f){
	in[v] = tim++;
	for(auto [u,w] : adj[v]){
		if(u == f) continue;
		dfs(u,v);
		p[u][0] = v, sm[u][0] = w; 
	}
	out[v] = tim++;
}

bool anc(int u,int v){
	return (in[u] <= in[v] and out[v] <= out[u]);
}

int lca(int u,int v){
	if(anc(u,v)) return u;
	if(anc(v,u)) return v;
	int al = u;
	fr(i,17,0){
		if(p[al][i] == -1) continue;
		if(!anc(p[al][i],v)) al = p[al][i];
	}
	return p[al][0];
}

int dis(int u,int v){
	// u to v
	if(anc(u,v)) return 0;
	int al = u, ans = 0;
	fr(i,17,0){
		if(p[al][i] == -1) continue;
		if(!anc(p[al][i],v)){
			ans += sm[al][i], al = p[al][i];
		} 
	}
	ans += sm[al][0];
	return ans;
}

map<int,int> ch;
int wn[15];
vi n_adj[15];

int com(int v,int f){
	int ans = 0;
	for(auto u : n_adj[v]){
		if(u == f) continue;
		ans += dis(wn[u],wn[v]);
		ans += com(u,v);
	}
	return ans;
}

int build(set<int> v){
	int cr = -1;
	for(auto it : v){
		if(cr == -1){
			cr = it;
			continue;
		} 
		if(anc(cr,it)) continue;
		if(anc(it,cr)) cr = it;
		else cr = -1;
	}
	v.erase(cr);
	vector<set<int>> sn;
	for(auto it : v){
		bool fl = 1;
		for(auto &go : sn){
			int fv = *go.begin();
			if(lca(fv,it) != cr){
				fl = 0;
				go.insert(it);
				break;
			} 
		}
		if(!fl) continue;
		set<int> ngo = {it};
		sn.push_back(ngo);
	}
	for(auto go : sn){
		int sv = build(go);
		n_adj[ch[cr]].push_back(sv);
		n_adj[sv].push_back(ch[cr]);
	}
	return ch[cr];
}

int go(vi v){
	ch.clear();
	f(i,0,12){
		wn[i] = 0; n_adj[i].clear();
	}
	set<int> nv;
	f(i,0,sz(v)) f(j,i,sz(v)) nv.insert(lca(v[i],v[j]));
	int ct = 0;
	for(auto it : nv) ch[it] = ct, wn[ct] = it, ct++;
	int root = build(nv);
	return com(root,-1);
}

void solve(){
	cin >> n;
	f(i,1,n){
		int u,v,w; cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	p[0][0] = -1;
	dfs(0,-1);
	f(j,1,18){
		f(i,0,n){
			if(p[i][j-1] == -1 or p[p[i][j-1]][j-1] == -1){
				p[i][j] = -1; continue;
			}  
			p[i][j] = p[p[i][j-1]][j-1], sm[i][j] = sm[i][j-1]+sm[p[i][j-1]][j-1];
			// cout << i << " " << j << " " << p[i][j] << " " << sm[i][j] << endl;
		} 
	}
	// cout << dis(3,0) << endl;
	int q; cin >> q;
	f(i,0,q){
		vi v(5);
		for(auto &it : v) cin >> it;
		cout << go(v) << endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
	// cin >> tc;
	while(tc--) solve();	
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30