Submission #538994


Source Code Expand

// tsukasa_diary's programing contest code template
#include <bits/stdc++.h>
using namespace std;
#define TSUKASA_DIARY_S_TEMPLATE
// define
#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
#define allof(a) (a).begin(),(a).end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) int((a).size())
#define cauto const auto
// typedef
typedef long long lint;
typedef double Double;
typedef pair< int, int > pii;
template< typename T > using Vec = vector< T >;
template< typename T > using Matrix = Vec< Vec< T > >;
template< typename T > using USet = unordered_set< T >;
template< typename T, class C > using MyUSet = unordered_set< T, C >;
template< typename T, typename F > using UMap = unordered_map< T, F >;
template< typename T, typename F, class C > using MyUMap = unordered_map< T, F, C >;
// hash
class PiiHash { public: size_t operator () (const pii& p) const { return (p.first << 16) | p.second; } };
// popcount
inline int POPCNT(int x) { return __builtin_popcount(x); }
inline int POPCNT(lint x) { return __builtin_popcount(x); }
// inf
const int iINF = 1L << 30;
const lint lINF = 1LL << 60;
// eps
const Double EPS = 1e-9;
const Double PI = acos(-1);
// inrange
template< typename T >
inline bool in_range(T v, T mi, T mx) { return mi <= v && v < mx; }
template< typename T >
inline bool in_range(T x, T y, T W, T H) { return in_range(x,0,W) && in_range(y,0,H); }
// neighbor clockwise
const int DX[4] = {0,1,0,-1}, DY[4] = {-1,0,1,0};
const int DX_[8] = {0,1,1,1,0,-1,-1,-1}, DY_[8] = {-1,-1,0,1,1,1,0,-1};
// variable update
template< typename T > inline void modAdd(T& a, T b, T mod) { a = (a + b) % mod; }
template< typename T > inline void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > inline void maxUpdate(T& a, T b) { a = max(a, b); }
// converter
template< typename F, typename T >
inline void convert(F& from, T& to) {
	stringstream ss;
	ss << from; ss >> to;
}

// Heavy Light Decomposition
class H_L_Decomp {
public:
	struct Node {
		int parent;
		Vec< int > path;
		Vec< int > adj;
	};
	
	struct VertexInfo { int nodeID, pos; };
	
	struct Result {
		Vec< Node > nodes;
		Vec< VertexInfo > vinfo;
	};
	
private:
	int N;
	const Vec< Vec< int > >& adj;
	
	Vec< Node > nodes;
	Vec< VertexInfo > vinfo;
	Vec< pii > part_max;
	
	int partDfs(int v, int p) {
		int part = 1;
		
		for (int u : adj[v]) {
			if (u != p) {
				int nxt = partDfs(u, v);
				maxUpdate(part_max[v], pii(nxt, u));
				part += nxt;
			}
		}
		
		return part;
	}
	
	void decompDfs(int v, int p) {		
		vinfo[v].nodeID = nodes.size() - 1;
		vinfo[v].pos = nodes[ nodes.size() - 1 ].path.size();
		
		nodes[ nodes.size() - 1 ].path.push_back(v);
		
		if (part_max[v].second != -1) {
			decompDfs(part_max[v].second, v);
			
			for (int u : adj[v]) {
				if (u != p && u != part_max[v].second) {
					nodes[ vinfo[v].nodeID ].adj.push_back(nodes.size());
					nodes.push_back(Node{v, Vec< int >(), Vec< int >()});
					
					decompDfs(u, v);
				}
			}
		}
	}
	
public:
	H_L_Decomp(const Vec< Vec< int > >& _adj_) : N(_adj_.size()), adj(_adj_) {}
	
	Result decomposition(int root) {
		part_max.assign(N, pii(-1, -1));
		
		partDfs(root, -1);
		
		nodes.clear();
		nodes.push_back(Node{-1, Vec< int >(), Vec< int >()});
		
		vinfo = Vec< VertexInfo >(N);
		
		decompDfs(root, -1);
		
		return Result{nodes, vinfo};
	}
};

// lowest common ancester
class LCA {
public:
	struct Result {
		vector< int > depth;
		
		int K;
		vector< vector< int > > parent;
		
		int getLCA(int u, int v) {
			if (depth[u] > depth[v]) swap(u, v);
			
			for_(k,0,K) if ((depth[v] - depth[u]) >> k & 1) v = parent[v][k];
			
			if (u == v) return u;
			
			for_rev(k,K-1,0) {
				if (parent[u][k] != parent[v][k]) {
					u = parent[u][k];
					v = parent[v][k];
				}
			}
			
			return parent[u][0];
		}
	};
	
private:
	int N;
	const vector< vector< int > >& adj;
	
	vector< int > depth;
	vector< vector< int > > parent;
	
	void depthDfs(int v, int p) {
		depth[v] = (p == -1) ? 0 : depth[p] + 1;
		parent[v][0] = p;
		for (int u : adj[v]) if (u != p) depthDfs(u, v);
	}
	
public:
	LCA(const vector< vector< int > >& _adj_) : N(_adj_.size()), adj(_adj_) {}
	
	Result generate(int root) {
		depth.assign(N, 0);
		
		int S = 1, K = 1;
		for (; S < N; S <<= 1) ++K;
		
		parent.assign(N, vector< int >(K, -1));
		
		depthDfs(root, -1);
		
		for_(k,0,K-1) for_(v,0,N) {
			if (parent[v][k] < 0) parent[v][k + 1] = -1;
			else parent[v][k + 1] = parent[ parent[v][k] ][k];
		}
		
		return Result{depth, K, parent};
	}
};

// Segment Tree
template< typename DATA >
class SegmentTree {
private:
	int size__;
	Vec< DATA > data;
	
	inline int left_t(int k) { return (k << 1) + 1; }
	inline int right_t(int k) { return (k << 1) + 2; }
	inline int center(int l, int r) { return (l + r) >> 1; }
	
	DATA calc(DATA d1, DATA d2) { return min(d1, d2); }
	
	DATA query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return (DATA)iINF;
		if (a <= l && r <= b) return data[k];
		return calc(query(a, b, left_t(k), l, center(l, r)),
					query(a, b, right_t(k), center(l, r), r));
	}
	
public:
	SegmentTree(int n, DATA ini) {
		for (size__ = 1; size__ < n; size__ <<= 1);
		data.assign(2 * size__ - 1, ini);
	}
	
	void update(int k, DATA a) {
		k += size__ - 1;
		data[k] = a;
		
		while (k > 0) {
			k = (k - 1) >> 1;
			data[k] = calc(data[left_t(k)], data[right_t(k)]);
		}
	}
	
	DATA query(int a, int b) { return query(a, b, 0, 0, size__); }
	
	int size() { return size__; }
};

int n, q, a[100010];
vector< vector< int > > adj;
vector< SegmentTree< int > > segv;

void upmod(H_L_Decomp::Result& hld, int from, int to, int& x) {
	int v = from;
	int end_node_id = hld.vinfo[to].nodeID;
	
	while (x > 0) {
		int cur_node_id = hld.vinfo[v].nodeID;
		
		int lb = (cur_node_id == end_node_id ? hld.vinfo[to].pos : 0);
		int lst = hld.vinfo[v].pos + 1;
		int ub = lst;
		
		while (ub - lb > 1) {
			int med = (ub + lb) / 2;
			
			int mina = segv[cur_node_id].query(med, lst);
			
			if (mina > x) ub = med;
			else lb = med;
		}
		
		int u = hld.nodes[cur_node_id].path[lb];
		x %= a[u];
		v = u;
		
		if (v == to) break;
		
		if (v == hld.nodes[cur_node_id].path[0]) {
			v = hld.nodes[cur_node_id].parent;
		}
	}
}

void downmod(H_L_Decomp::Result& hld, int from, int to, int& x) {
	Vec< int > check_point;
	Vec< int > nxt_v;
	
	int v = to;
	int end_node_id = hld.vinfo[from].nodeID;
	
	while (v != from) {
		check_point.push_back(v);
		int cur_node_id = hld.vinfo[v].nodeID;
		nxt_v.push_back((cur_node_id == end_node_id ? from : hld.nodes[cur_node_id].path[0]));
		v = (cur_node_id == end_node_id ? from : hld.nodes[cur_node_id].parent);
	}
	
	check_point.push_back(from);
	nxt_v.push_back(-1);
	
	reverse(allof(check_point));
	reverse(allof(nxt_v));
	
	v = from;
	int i = 0;
	
	while (x > 0) {
		int cur_node_id = hld.vinfo[v].nodeID;
		
		int fst = hld.vinfo[v].pos;
		int cp = check_point[i];
		
		int lb = fst;
		int ub = hld.vinfo[cp].pos + 1;
		
		while (ub - lb > 1) {
			int med = (ub + lb) / 2;
			
			int mina = segv[cur_node_id].query(fst, med);
			
			if (mina > x) lb = med;
			else ub = med;
		}
		
		int u = hld.nodes[cur_node_id].path[ub - 1];
		x %= a[u];
		v = u;
		
		if (v == to) break;
		
		if (v == cp) {
			++i;
			v = nxt_v[i];
		}
	}
}

int main() {
	cin >> n >> q;
	for_(i,0,n) cin >> a[i];
	
	adj.assign(n, vector< int >());
	
	for_(i,0,n-1) {
		int b, c;
		cin >> b >> c;
		--b; --c;
		adj[b].push_back(c);
		adj[c].push_back(b);
	}
	
	LCA::Result lca = LCA(adj).generate(0);
	
	H_L_Decomp::Result hld = H_L_Decomp(adj).decomposition(0);
	
	int M = hld.nodes.size();
	
	for_(i,0,M) {
		segv.push_back(SegmentTree< int >(hld.nodes[i].path.size(), iINF));
		
		int j = 0;
		
		for (int v : hld.nodes[i].path) {
			segv[i].update(j, a[v]);
			++j;
		}
	}
	
	for_(i,0,q) {
		int x, v, w;
		cin >> x >> v >> w;
		--v; --w;
		
		int u = lca.getLCA(v, w);
		
		upmod(hld, v, u, x);
		downmod(hld, u, w, x);
		
		cout << x << endl;
	}
}

Submission Info

Submission Time
Task J - MODクエリ
User tsukasa_diary
Language C++11 (GCC 4.9.2)
Score 400
Code Size 8352 Byte
Status AC
Exec Time 2387 ms
Memory 45348 KB

Judge Result

Set Name Small All
Score / Max Score 30 / 30 370 / 370
Status
AC × 16
AC × 38
Set Name Test Cases
Small 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt
All 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt, 20_random_15.txt, 20_random_16.txt, 20_random_17.txt, 21_random_18.txt, 21_random_19.txt, 21_random_20.txt, 30_random_21.txt, 30_random_22.txt, 30_random_23.txt, 40_random_24.txt, 40_random_25.txt, 40_random_26.txt, 49_sample_02.txt, 61_test_27.txt, 61_test_28.txt, 61_test_29.txt, 63_star_30.txt, 63_star_31.txt, 63_star_32.txt, 64_three_33.txt, 64_three_34.txt, 64_three_35.txt
Case Name Status Exec Time Memory
00_sample_path_01.txt AC 41 ms 796 KB
15_path_00.txt AC 42 ms 928 KB
15_path_01.txt AC 38 ms 924 KB
15_path_02.txt AC 27 ms 808 KB
15_path_03.txt AC 27 ms 796 KB
15_path_04.txt AC 26 ms 924 KB
16_path_05.txt AC 27 ms 928 KB
16_path_06.txt AC 29 ms 928 KB
16_path_07.txt AC 28 ms 804 KB
16_path_08.txt AC 28 ms 804 KB
16_path_09.txt AC 26 ms 920 KB
17_path_10.txt AC 2228 ms 45292 KB
17_path_11.txt AC 2165 ms 45292 KB
17_path_12.txt AC 2250 ms 45348 KB
17_path_13.txt AC 2217 ms 45348 KB
17_path_14.txt AC 2150 ms 45300 KB
20_random_15.txt AC 26 ms 868 KB
20_random_16.txt AC 27 ms 920 KB
20_random_17.txt AC 27 ms 916 KB
21_random_18.txt AC 29 ms 920 KB
21_random_19.txt AC 29 ms 920 KB
21_random_20.txt AC 27 ms 940 KB
30_random_21.txt AC 28 ms 808 KB
30_random_22.txt AC 26 ms 804 KB
30_random_23.txt AC 26 ms 808 KB
40_random_24.txt AC 1520 ms 29352 KB
40_random_25.txt AC 1432 ms 29416 KB
40_random_26.txt AC 1350 ms 29416 KB
49_sample_02.txt AC 26 ms 932 KB
61_test_27.txt AC 2132 ms 36856 KB
61_test_28.txt AC 2103 ms 36900 KB
61_test_29.txt AC 2269 ms 33072 KB
63_star_30.txt AC 1064 ms 38000 KB
63_star_31.txt AC 1045 ms 37984 KB
63_star_32.txt AC 1118 ms 38044 KB
64_three_33.txt AC 2387 ms 37036 KB
64_three_34.txt AC 2345 ms 38512 KB
64_three_35.txt AC 2367 ms 35120 KB