oj.uz

Submission #588658

# Submission time Handle Problem Language Result Execution time Memory
588658 2022-07-03T19:30:36 Z angelo_torres Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 136 ms 15500 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 13592 KB Output is correct
2 Correct 93 ms 15416 KB Output is correct
3 Correct 103 ms 15492 KB Output is correct
4 Correct 99 ms 15500 KB Output is correct
5 Correct 96 ms 15488 KB Output is correct
6 Correct 96 ms 15416 KB Output is correct
7 Correct 96 ms 15468 KB Output is correct
8 Correct 111 ms 15440 KB Output is correct
9 Correct 99 ms 15428 KB Output is correct
10 Correct 120 ms 15452 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11532 KB Output is correct
2 Correct 36 ms 14420 KB Output is correct
3 Correct 37 ms 14528 KB Output is correct
4 Correct 38 ms 14516 KB Output is correct
5 Correct 35 ms 14416 KB Output is correct
6 Correct 37 ms 14516 KB Output is correct
7 Correct 36 ms 14420 KB Output is correct
8 Correct 46 ms 14452 KB Output is correct
9 Correct 42 ms 14500 KB Output is correct
10 Correct 35 ms 14420 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 128 ms 13592 KB Output is correct
3 Correct 93 ms 15416 KB Output is correct
4 Correct 103 ms 15492 KB Output is correct
5 Correct 99 ms 15500 KB Output is correct
6 Correct 96 ms 15488 KB Output is correct
7 Correct 96 ms 15416 KB Output is correct
8 Correct 96 ms 15468 KB Output is correct
9 Correct 111 ms 15440 KB Output is correct
10 Correct 99 ms 15428 KB Output is correct
11 Correct 120 ms 15452 KB Output is correct
12 Correct 29 ms 11532 KB Output is correct
13 Correct 36 ms 14420 KB Output is correct
14 Correct 37 ms 14528 KB Output is correct
15 Correct 38 ms 14516 KB Output is correct
16 Correct 35 ms 14416 KB Output is correct
17 Correct 37 ms 14516 KB Output is correct
18 Correct 36 ms 14420 KB Output is correct
19 Correct 46 ms 14452 KB Output is correct
20 Correct 42 ms 14500 KB Output is correct
21 Correct 35 ms 14420 KB Output is correct
22 Correct 109 ms 13680 KB Output is correct
23 Correct 119 ms 11960 KB Output is correct
24 Correct 119 ms 14824 KB Output is correct
25 Correct 136 ms 14884 KB Output is correct
26 Correct 114 ms 14772 KB Output is correct
27 Correct 123 ms 14880 KB Output is correct
28 Correct 117 ms 14868 KB Output is correct
29 Correct 118 ms 14828 KB Output is correct
30 Correct 119 ms 14872 KB Output is correct
31 Correct 116 ms 14804 KB Output is correct