oj.uz

Submission #706703

# Submission time Handle Problem Language Result Execution time Memory
706703 2023-03-07T12:22:36 Z attemptn63 Construction of Highway (JOI18_construction) C++17
100 / 100
 375 ms 110264 KB 
#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 int long long
#define double long double
#define endl '\n'
#define all(k) (k).begin(), (k).end()
#define pb push_back
#define fi first
#define se second
#define sz(k) (int)(k).size()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pi pair<long long, long long>
#define mp make_pair
#define ti tuple<long long, long long, long long>
#define INF (long long)1e18
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
#define sign(x) ((x > 0) - (x < 0))
template <class T>using vec = vector<T>;
template <class T>using min_heap = priority_queue<T, vec<T>, greater<T>>;
template <class T>using max_heap = priority_queue<T>;
template <class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef DEBUG
template <typename T>
inline void debug(T k){
	cout << k << " ";
}
template <typename T, typename... Args>
inline void debug(T k, Args... args){
	cout << k << " | ";
	debug(args...);
}
#define debug(...) cout << "[" << #__VA_ARGS__ << "] : ";debug(__VA_ARGS__);cout << endl
template <typename T>
ostream &operator<<(ostream &o_str, const vec<T> &p){
	o_str << "{ ";
	for (auto i = 0; i < (int)p.size(); i++){
		o_str << p[i];
		if (i < (int)p.size() - 1){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T>
ostream &operator<<(ostream &o_str, const deque<T> &p){
	o_str << "{ ";
	for (auto i = 0; i < (int)p.size(); i++){
		o_str << p[i];
		if (i < (int)p.size() - 1){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const pair<T, U> &p){
	return o_str << "(" << p.fi << ", " << p.se << ")";
}
template <typename T, typename U, typename V>
ostream &operator<<(ostream &o_str, const tuple<T, U, V> &p){
	return o_str << "(" << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ")";
}
template <typename T>
ostream &operator<<(ostream &o_str, const set<T> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << *i;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const map<T, U> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << i->first << ": " << i->second;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T>
ostream &operator<<(ostream &o_str, const queue<T> &p){
	queue<T> q = p;
	o_str << "{ ";
	while (!q.empty()){
		o_str << q.front();
		q.pop();
		if (!q.empty()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U, typename cmp>
ostream &operator<<(ostream &o_str, const priority_queue<T,U,cmp> &p){
	priority_queue<T,U,cmp> q = p;
	o_str << "{ ";
	while (!q.empty()){
		o_str << q.top();
		q.pop();
		if (!q.empty()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const set<T, U> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << *i;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template<typename T, typename U>
ostream &operator<<(ostream &o_str, const multiset<T, U> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << *i;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const unordered_map<T, U> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << i->first << ": " << i->second;
		o_str << ", ";
	}
	return o_str << " }" << endl;
}
#else
template <typename T>
inline void debug(T k){}
template <typename T, typename... Args>
inline void debug(T k, Args... args) {}
#define debug(...)
template <typename T>
ostream &operator<<(ostream &o_str, const vec<T> &p){return o_str;}
template <typename T>
ostream &operator<<(ostream &o_str, const deque<T> &p) { return o_str; }
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const pair<T, U> &p) { return o_str; }
template <typename T, typename U, typename V>
ostream &operator<<(ostream &o_str, const tuple<T, U, V> &p) { return o_str; }
template <typename T>
ostream &operator<<(ostream &o_str, const set<T> &p) { return o_str; }
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const map<T, U> &p) { return o_str; }
template <typename T>
ostream &operator<<(ostream &o_str, const queue<T> &p) { return o_str; }
template <typename T, typename U, typename cmp>
ostream &operator<<(ostream &o_str, const priority_queue<T,U,cmp> &p){return o_str;}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const set<T, U> &p) { return o_str; }
template<typename T, typename U>
ostream &operator<<(ostream &o_str, const multiset<T, U> &p) { return o_str; }
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const unordered_map<T, U> &p) { return o_str; }
#endif

int n, val[100005],depth[100005],sz[100005],hpar[100005],par[100005];
deque<pi> hld[100005];
vec<int> adj[100005],disc;
vec<pi> edges,chain;
void dfs_sz(int i,int p){
	sz[i] = 1;
	for(auto &j: adj[i]){
		if(j == p) continue;
		par[j] = i;
		depth[j] = depth[i] + 1;
		dfs_sz(j,i);
		sz[i] += sz[j];
		if(sz[j] > sz[adj[i][0]]) swap(j,adj[i][0]);
	}
}
void dfs_hld(int i,int p){
	for(auto it: adj[i]){
		if(it == p) continue;
		if(it == adj[i][0]) hpar[it] = hpar[i];
		else hpar[it] = it;
		dfs_hld(it,i);
	}
}

int bit[100005];
void init(int n){
	for(int i = 0;i<=n;i++) bit[i] = 0;
}
void upd(int i,int v){
	i++;
	for(;i<=n;i+=(i&-i)) bit[i] += v;
}
int qry(int i){
	i++;
	int ret = 0;
	for(;i;i-=(i&-i)) ret += bit[i];
	return ret;
}

signed main(){
	speed;
	cin >> n;
	for(int i = 0;i<n;i++) cin >> val[i];
	hpar[0] = 0;
	par[0] = -1;
	hld[0].push_back({val[0],1LL});
	for(int i = 0;i<n-1;i++){
		int a,b; cin >> a >> b; a--; b--;
		adj[a].push_back(b);
		edges.push_back({a,b});
	}
	dfs_sz(0,-1);
	dfs_hld(0,-1);
	for(int i = 0;i<n-1;i++){
		chain.clear();
		disc.clear();
		int a = edges[i].fi;
		while(a != -1){
			int apar = hpar[a];
			int dpt = depth[a] - depth[apar] + 1;
			vec<pi> temp;
			for(int k = 0;k<sz(hld[apar]);k++){	
				auto [cnt,v] = hld[apar][k];
				if(cnt <= dpt){
					dpt -= cnt;
					temp.push_back({cnt,v});
				}
				else{
					temp.push_back({dpt,v});
					break;
				}
			}
			for(int i = sz(temp)-1;i>=0;i--){
				chain.push_back(temp[i]);
				disc.push_back(temp[i].second);
			}
			a = par[apar];
		}
		reverse(all(chain));
		sort(all(disc));
		disc.erase(unique(all(disc)),disc.end());
		init(sz(disc));
		int ans = 0,mx = 0;	
		for(auto [u,v]: chain){
			v = lower_bound(all(disc),v) - disc.begin();
			ans += u * (mx - qry(v));
			mx += u;
			upd(v,u);
		}
		cout << ans << endl;
		if(i == n-2) return 0;
		int u = edges[i].se;
		while(u != -1){
			int upar = hpar[u];
			int dpt = depth[u] - depth[upar] + 1;
			while(sz(hld[upar]) > 0){
				int cnt = hld[upar][0].first;
				if(cnt <= dpt){
					dpt -= cnt;
					hld[upar].pop_front();
				}
				else{
					hld[upar][0].first -= dpt;
					break;
				}
			}
			hld[upar].push_front({depth[u] - depth[upar] + 1,val[edges[i].se]});
			u = par[upar];
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 69972 KB Output is correct
2 Correct 44 ms 69996 KB Output is correct
3 Correct 42 ms 70056 KB Output is correct
4 Correct 47 ms 70092 KB Output is correct
5 Correct 43 ms 70188 KB Output is correct
6 Correct 44 ms 70100 KB Output is correct
7 Correct 43 ms 70100 KB Output is correct
8 Correct 41 ms 70084 KB Output is correct
9 Correct 39 ms 70024 KB Output is correct
10 Correct 39 ms 69988 KB Output is correct
11 Correct 42 ms 70224 KB Output is correct
12 Correct 46 ms 70244 KB Output is correct
13 Correct 45 ms 70216 KB Output is correct
14 Correct 45 ms 70188 KB Output is correct
15 Correct 43 ms 70120 KB Output is correct
16 Correct 44 ms 70160 KB Output is correct
17 Correct 43 ms 70124 KB Output is correct
18 Correct 44 ms 70092 KB Output is correct
19 Correct 43 ms 70116 KB Output is correct
20 Correct 42 ms 70092 KB Output is correct
21 Correct 43 ms 70184 KB Output is correct
22 Correct 44 ms 70188 KB Output is correct
23 Correct 43 ms 70092 KB Output is correct
24 Correct 45 ms 70184 KB Output is correct
25 Correct 42 ms 70112 KB Output is correct
26 Correct 39 ms 70028 KB Output is correct
27 Correct 43 ms 70228 KB Output is correct
28 Correct 42 ms 70180 KB Output is correct
29 Correct 44 ms 70152 KB Output is correct
30 Correct 44 ms 70184 KB Output is correct
31 Correct 42 ms 70100 KB Output is correct
32 Correct 44 ms 70196 KB Output is correct
33 Correct 42 ms 70196 KB Output is correct
34 Correct 43 ms 70164 KB Output is correct
35 Correct 42 ms 70108 KB Output is correct
36 Correct 43 ms 70100 KB Output is correct
37 Correct 43 ms 70140 KB Output is correct
38 Correct 44 ms 70176 KB Output is correct
39 Correct 44 ms 70184 KB Output is correct
40 Correct 43 ms 70100 KB Output is correct
41 Correct 43 ms 70156 KB Output is correct
42 Correct 42 ms 70136 KB Output is correct
43 Correct 43 ms 70180 KB Output is correct
44 Correct 44 ms 70180 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 69972 KB Output is correct
2 Correct 44 ms 69996 KB Output is correct
3 Correct 42 ms 70056 KB Output is correct
4 Correct 47 ms 70092 KB Output is correct
5 Correct 43 ms 70188 KB Output is correct
6 Correct 44 ms 70100 KB Output is correct
7 Correct 43 ms 70100 KB Output is correct
8 Correct 41 ms 70084 KB Output is correct
9 Correct 39 ms 70024 KB Output is correct
10 Correct 39 ms 69988 KB Output is correct
11 Correct 42 ms 70224 KB Output is correct
12 Correct 46 ms 70244 KB Output is correct
13 Correct 45 ms 70216 KB Output is correct
14 Correct 45 ms 70188 KB Output is correct
15 Correct 43 ms 70120 KB Output is correct
16 Correct 44 ms 70160 KB Output is correct
17 Correct 43 ms 70124 KB Output is correct
18 Correct 44 ms 70092 KB Output is correct
19 Correct 43 ms 70116 KB Output is correct
20 Correct 42 ms 70092 KB Output is correct
21 Correct 43 ms 70184 KB Output is correct
22 Correct 44 ms 70188 KB Output is correct
23 Correct 43 ms 70092 KB Output is correct
24 Correct 45 ms 70184 KB Output is correct
25 Correct 42 ms 70112 KB Output is correct
26 Correct 39 ms 70028 KB Output is correct
27 Correct 43 ms 70228 KB Output is correct
28 Correct 42 ms 70180 KB Output is correct
29 Correct 44 ms 70152 KB Output is correct
30 Correct 44 ms 70184 KB Output is correct
31 Correct 42 ms 70100 KB Output is correct
32 Correct 44 ms 70196 KB Output is correct
33 Correct 42 ms 70196 KB Output is correct
34 Correct 43 ms 70164 KB Output is correct
35 Correct 42 ms 70108 KB Output is correct
36 Correct 43 ms 70100 KB Output is correct
37 Correct 43 ms 70140 KB Output is correct
38 Correct 44 ms 70176 KB Output is correct
39 Correct 44 ms 70184 KB Output is correct
40 Correct 43 ms 70100 KB Output is correct
41 Correct 43 ms 70156 KB Output is correct
42 Correct 42 ms 70136 KB Output is correct
43 Correct 43 ms 70180 KB Output is correct
44 Correct 44 ms 70180 KB Output is correct
45 Correct 43 ms 70356 KB Output is correct
46 Correct 51 ms 71352 KB Output is correct
47 Correct 50 ms 71316 KB Output is correct
48 Correct 49 ms 71304 KB Output is correct
49 Correct 41 ms 70620 KB Output is correct
50 Correct 41 ms 70524 KB Output is correct
51 Correct 41 ms 70600 KB Output is correct
52 Correct 46 ms 71580 KB Output is correct
53 Correct 45 ms 71608 KB Output is correct
54 Correct 46 ms 71500 KB Output is correct
55 Correct 45 ms 71700 KB Output is correct
56 Correct 45 ms 71484 KB Output is correct
57 Correct 47 ms 71244 KB Output is correct
58 Correct 50 ms 71260 KB Output is correct
59 Correct 49 ms 71220 KB Output is correct
60 Correct 51 ms 71332 KB Output is correct
61 Correct 48 ms 71436 KB Output is correct
62 Correct 45 ms 71424 KB Output is correct
63 Correct 47 ms 71380 KB Output is correct
64 Correct 47 ms 71340 KB Output is correct
65 Correct 48 ms 71320 KB Output is correct
66 Correct 48 ms 71336 KB Output is correct
67 Correct 47 ms 71304 KB Output is correct
68 Correct 40 ms 70628 KB Output is correct
69 Correct 45 ms 71508 KB Output is correct
70 Correct 48 ms 71704 KB Output is correct
71 Correct 45 ms 71372 KB Output is correct
72 Correct 49 ms 71252 KB Output is correct
73 Correct 50 ms 71312 KB Output is correct
74 Correct 45 ms 71488 KB Output is correct
75 Correct 46 ms 71332 KB Output is correct
76 Correct 46 ms 71368 KB Output is correct
77 Correct 46 ms 71388 KB Output is correct
78 Correct 46 ms 71372 KB Output is correct
79 Correct 47 ms 71292 KB Output is correct
80 Correct 46 ms 71368 KB Output is correct
81 Correct 45 ms 71316 KB Output is correct
82 Correct 46 ms 71380 KB Output is correct
83 Correct 47 ms 71384 KB Output is correct
84 Correct 46 ms 71408 KB Output is correct
85 Correct 47 ms 71380 KB Output is correct
86 Correct 46 ms 71268 KB Output is correct

Subtask #3
84.0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 69972 KB Output is correct
2 Correct 44 ms 69996 KB Output is correct
3 Correct 42 ms 70056 KB Output is correct
4 Correct 47 ms 70092 KB Output is correct
5 Correct 43 ms 70188 KB Output is correct
6 Correct 44 ms 70100 KB Output is correct
7 Correct 43 ms 70100 KB Output is correct
8 Correct 41 ms 70084 KB Output is correct
9 Correct 39 ms 70024 KB Output is correct
10 Correct 39 ms 69988 KB Output is correct
11 Correct 42 ms 70224 KB Output is correct
12 Correct 46 ms 70244 KB Output is correct
13 Correct 45 ms 70216 KB Output is correct
14 Correct 45 ms 70188 KB Output is correct
15 Correct 43 ms 70120 KB Output is correct
16 Correct 44 ms 70160 KB Output is correct
17 Correct 43 ms 70124 KB Output is correct
18 Correct 44 ms 70092 KB Output is correct
19 Correct 43 ms 70116 KB Output is correct
20 Correct 42 ms 70092 KB Output is correct
21 Correct 43 ms 70184 KB Output is correct
22 Correct 44 ms 70188 KB Output is correct
23 Correct 43 ms 70092 KB Output is correct
24 Correct 45 ms 70184 KB Output is correct
25 Correct 42 ms 70112 KB Output is correct
26 Correct 39 ms 70028 KB Output is correct
27 Correct 43 ms 70228 KB Output is correct
28 Correct 42 ms 70180 KB Output is correct
29 Correct 44 ms 70152 KB Output is correct
30 Correct 44 ms 70184 KB Output is correct
31 Correct 42 ms 70100 KB Output is correct
32 Correct 44 ms 70196 KB Output is correct
33 Correct 42 ms 70196 KB Output is correct
34 Correct 43 ms 70164 KB Output is correct
35 Correct 42 ms 70108 KB Output is correct
36 Correct 43 ms 70100 KB Output is correct
37 Correct 43 ms 70140 KB Output is correct
38 Correct 44 ms 70176 KB Output is correct
39 Correct 44 ms 70184 KB Output is correct
40 Correct 43 ms 70100 KB Output is correct
41 Correct 43 ms 70156 KB Output is correct
42 Correct 42 ms 70136 KB Output is correct
43 Correct 43 ms 70180 KB Output is correct
44 Correct 44 ms 70180 KB Output is correct
45 Correct 43 ms 70356 KB Output is correct
46 Correct 51 ms 71352 KB Output is correct
47 Correct 50 ms 71316 KB Output is correct
48 Correct 49 ms 71304 KB Output is correct
49 Correct 41 ms 70620 KB Output is correct
50 Correct 41 ms 70524 KB Output is correct
51 Correct 41 ms 70600 KB Output is correct
52 Correct 46 ms 71580 KB Output is correct
53 Correct 45 ms 71608 KB Output is correct
54 Correct 46 ms 71500 KB Output is correct
55 Correct 45 ms 71700 KB Output is correct
56 Correct 45 ms 71484 KB Output is correct
57 Correct 47 ms 71244 KB Output is correct
58 Correct 50 ms 71260 KB Output is correct
59 Correct 49 ms 71220 KB Output is correct
60 Correct 51 ms 71332 KB Output is correct
61 Correct 48 ms 71436 KB Output is correct
62 Correct 45 ms 71424 KB Output is correct
63 Correct 47 ms 71380 KB Output is correct
64 Correct 47 ms 71340 KB Output is correct
65 Correct 48 ms 71320 KB Output is correct
66 Correct 48 ms 71336 KB Output is correct
67 Correct 47 ms 71304 KB Output is correct
68 Correct 40 ms 70628 KB Output is correct
69 Correct 45 ms 71508 KB Output is correct
70 Correct 48 ms 71704 KB Output is correct
71 Correct 45 ms 71372 KB Output is correct
72 Correct 49 ms 71252 KB Output is correct
73 Correct 50 ms 71312 KB Output is correct
74 Correct 45 ms 71488 KB Output is correct
75 Correct 46 ms 71332 KB Output is correct
76 Correct 46 ms 71368 KB Output is correct
77 Correct 46 ms 71388 KB Output is correct
78 Correct 46 ms 71372 KB Output is correct
79 Correct 47 ms 71292 KB Output is correct
80 Correct 46 ms 71368 KB Output is correct
81 Correct 45 ms 71316 KB Output is correct
82 Correct 46 ms 71380 KB Output is correct
83 Correct 47 ms 71384 KB Output is correct
84 Correct 46 ms 71408 KB Output is correct
85 Correct 47 ms 71380 KB Output is correct
86 Correct 46 ms 71268 KB Output is correct
87 Correct 59 ms 73292 KB Output is correct
88 Correct 95 ms 80032 KB Output is correct
89 Correct 262 ms 103444 KB Output is correct
90 Correct 255 ms 103448 KB Output is correct
91 Correct 251 ms 103548 KB Output is correct
92 Correct 109 ms 85092 KB Output is correct
93 Correct 108 ms 85028 KB Output is correct
94 Correct 105 ms 85000 KB Output is correct
95 Correct 139 ms 110008 KB Output is correct
96 Correct 152 ms 110008 KB Output is correct
97 Correct 147 ms 109996 KB Output is correct
98 Correct 159 ms 110264 KB Output is correct
99 Correct 146 ms 106348 KB Output is correct
100 Correct 285 ms 95664 KB Output is correct
101 Correct 375 ms 95672 KB Output is correct
102 Correct 332 ms 95672 KB Output is correct
103 Correct 349 ms 95652 KB Output is correct
104 Correct 164 ms 106304 KB Output is correct
105 Correct 153 ms 106340 KB Output is correct
106 Correct 166 ms 106292 KB Output is correct
107 Correct 239 ms 103440 KB Output is correct
108 Correct 264 ms 103508 KB Output is correct
109 Correct 280 ms 103552 KB Output is correct
110 Correct 95 ms 85064 KB Output is correct
111 Correct 136 ms 109960 KB Output is correct
112 Correct 137 ms 109624 KB Output is correct
113 Correct 134 ms 106376 KB Output is correct
114 Correct 284 ms 95672 KB Output is correct
115 Correct 318 ms 95652 KB Output is correct
116 Correct 149 ms 106320 KB Output is correct
117 Correct 151 ms 104776 KB Output is correct
118 Correct 151 ms 104224 KB Output is correct
119 Correct 159 ms 103972 KB Output is correct
120 Correct 154 ms 104580 KB Output is correct
121 Correct 185 ms 104148 KB Output is correct
122 Correct 157 ms 103992 KB Output is correct
123 Correct 162 ms 104732 KB Output is correct
124 Correct 167 ms 104188 KB Output is correct
125 Correct 161 ms 104008 KB Output is correct
126 Correct 159 ms 104740 KB Output is correct
127 Correct 157 ms 104192 KB Output is correct
128 Correct 184 ms 104040 KB Output is correct