Submission #535036
Source Code Expand
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <iterator>
#include <iostream>
namespace lc {
struct Edge {
int to;
explicit Edge(int to) : to(to) { }
};
}
namespace lc {
template <typename EdgeType>
class AdjacencyList {
public:
typedef std::vector<EdgeType> ListType;
private:
std::vector<ListType> m_lists;
public:
explicit AdjacencyList(int n = 0)
: m_lists(n)
{ }
int size() const { return m_lists.size(); }
template <typename... Args>
void add_edge(int u, Args&&... args){
m_lists[u].emplace_back(args...);
}
const ListType &operator[](int u) const { return m_lists[u]; }
};
}
namespace lc {
class HeavyLightDecomposer {
public:
struct Connection {
int local_index;
int child_path;
explicit Connection(int li = -1, int cp = -1) :
local_index(li), child_path(cp)
{ }
};
struct Segment {
int path;
int first;
int last;
explicit Segment(int path = -1, int first = -1, int last = -1) :
path(path), first(first), last(last)
{ }
};
private:
typedef std::pair<int, int> pii;
struct Path {
int parent_vertex;
std::vector<Connection> children;
std::vector<int> vertices;
int depth;
};
std::vector<Path> m_paths;
std::vector<int> m_path_ids;
std::vector<int> m_local_indices;
template <typename EdgeType>
std::vector<int> compute_subtree_size(
const AdjacencyList<EdgeType> &conn, int root) const
{
const int n = conn.size();
std::vector<int> subtree_size(n);
std::vector<bool> passed(n), gathered(n);
std::stack<pii> count_stack;
count_stack.push(pii(root, 0));
while(!count_stack.empty()){
const pii p = count_stack.top();
count_stack.pop();
const int u = p.first, i = p.second;
if(i == 0){
passed[u] = true;
count_stack.push(pii(u, 1));
for(size_t j = 0; j < conn[u].size(); ++j){
const int v = conn[u][j].to;
if(passed[v]){ continue; }
count_stack.push(pii(v, 0));
}
}else{
int sum = 1;
gathered[u] = true;
for(size_t j = 0; j < conn[u].size(); ++j){
const int v = conn[u][j].to;
if(!gathered[v]){ continue; }
sum += subtree_size[v];
}
subtree_size[u] = sum;
}
}
return subtree_size;
}
public:
template <typename EdgeType>
explicit HeavyLightDecomposer(
const AdjacencyList<EdgeType> &conn, int root = 0)
: m_paths(0)
, m_path_ids(conn.size(), -1)
, m_local_indices(conn.size(), -1)
{
const std::vector<int> subtree_size = compute_subtree_size(conn, root);
std::stack<pii> decompose_stack;
decompose_stack.push(pii(root, -1));
while(!decompose_stack.empty()){
const pii p = decompose_stack.top();
decompose_stack.pop();
const int parent_vertex = p.second;
const int pid = m_paths.size();
m_paths.push_back(Path());
Path &path = m_paths.back();
path.parent_vertex = parent_vertex;
if(parent_vertex >= 0){
const int parent_pid = m_path_ids[parent_vertex];
const int parent_index = m_local_indices[parent_vertex];
m_paths[parent_pid].children.push_back(
Connection(parent_index, pid));
path.depth = m_paths[parent_pid].depth + 1;
}else{
path.depth = 0;
}
int cur = p.first;
while(cur >= 0){
const int st_size = subtree_size[cur], threshold = st_size / 2;
m_path_ids[cur] = pid;
m_local_indices[cur] = path.vertices.size();
path.vertices.push_back(cur);
int heavy_edge = -1;
for(size_t i = 0; i < conn[cur].size(); ++i){
const int v = conn[cur][i].to;
if(subtree_size[v] > subtree_size[cur]){ continue; }
if(heavy_edge < 0 && subtree_size[v] >= threshold){
heavy_edge = v;
}else{
decompose_stack.push(pii(v, cur));
}
}
cur = heavy_edge;
}
}
}
int path_count() const { return m_paths.size(); }
int path_length(int p) const { return m_paths[p].vertices.size(); }
int path_depth(int p) const { return m_paths[p].depth; }
int parent_path_id(int p) const {
if(m_paths[p].parent_vertex < 0){ return -1; }
return m_path_ids[m_paths[p].parent_vertex];
}
int parent_local_index(int p) const {
if(m_paths[p].parent_vertex < 0){ return -1; }
return m_local_indices[m_paths[p].parent_vertex];
}
int path_id(int v) const { return m_path_ids[v]; }
int local_index(int v) const { return m_local_indices[v]; }
int vertex_id(int p, int i) const { return m_paths[p].vertices[i]; }
std::vector<Segment> shortest_path(int u, int v) const {
std::vector<Segment> usegs, vsegs, result;
int up = path_id(u), ul = local_index(u);
int vp = path_id(v), vl = local_index(v);
while(up != vp){
const bool update_u = path_depth(up) >= path_depth(vp);
const bool update_v = path_depth(up) <= path_depth(vp);
if(update_u){
usegs.push_back(Segment(up, 0, ul + 1));
ul = parent_local_index(up);
up = parent_path_id(up);
}
if(update_v){
vsegs.push_back(Segment(vp, 0, vl + 1));
vl = parent_local_index(vp);
vp = parent_path_id(vp);
}
}
for(int i = 0; i < static_cast<int>(usegs.size()); ++i){
const Segment &s = usegs[i];
result.push_back(Segment(s.path, s.last - 1, s.first - 1));
}
result.push_back(Segment(up, ul, vl + (ul > vl ? -1 : 1)));
for(int i = static_cast<int>(vsegs.size()) - 1; i >= 0; --i){
result.push_back(vsegs[i]);
}
return result;
}
};
}
using namespace std;
typedef lc::Edge Edge;
static const int INF = 1000000010;
class SegmentTree {
public:
typedef int value_type;
private:
int m_size;
std::vector<value_type> m_data;
void initialize(){
for(int i = m_size - 2; i >= 0; --i){
m_data[i] = min(m_data[i * 2 + 1], m_data[i * 2 + 2]);
}
}
value_type query(int a, int b, int k, int l, int r) const {
if(r <= a || b <= l){ return INF; }
if(a <= l && r <= b){ return m_data[k]; }
const value_type vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
const value_type vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
int query_left(int x, int a, int b, int k, int l, int r) const {
if(r <= a || b <= l){ return -1; }
if(k >= m_size - 1){ return k - (m_size - 1); }
const value_type vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
if(vl <= x){
return query_left(x, a, b, k * 2 + 1, l, (l + r) / 2);
}else{
return query_left(x, a, b, k * 2 + 2, (l + r) / 2, r);
}
}
int query_right(int x, int a, int b, int k, int l, int r) const {
if(r <= a || b <= l){ return -1; }
if(k >= m_size - 1){ return k - (m_size - 1); }
const value_type vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
if(vr <= x){
return query_right(x, a, b, k * 2 + 2, (l + r) / 2, r);
}else{
return query_right(x, a, b, k * 2 + 1, l, (l + r) / 2);
}
}
public:
template <typename Iterator>
SegmentTree(Iterator first, Iterator last) :
m_size(1), m_data()
{
const int n = std::distance(first, last);
while(m_size < n){ m_size *= 2; }
m_data.resize(m_size * 2 - 1, INF);
std::copy(first, last, m_data.begin() + m_size - 1);
initialize();
}
value_type query(int a, int b) const {
return query(a, b, 0, 0, m_size);
}
int query_left(int x, int a, int b) const {
return query_left(x, a, b, 0, 0, m_size);
}
int query_right(int x, int a, int b) const {
return query_right(x, a, b, 0, 0, m_size);
}
value_type operator[](int i) const {
return m_data[m_size - 1 + i];
}
};
int main(){
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
for(int i = 0; i < n; ++i){ cin >> a[i]; }
lc::AdjacencyList<Edge> graph(n);
for(int i = 0; i + 1 < n; ++i){
int b, c;
cin >> b >> c;
--b; --c;
graph.add_edge(b, c);
graph.add_edge(c, b);
}
lc::HeavyLightDecomposer decomp(graph);
vector<SegmentTree> ntables;
for(int i = 0; i < decomp.path_count(); ++i){
const int len = decomp.path_length(i);
vector<int> raw_path(len);
for(int j = 0; j < len; ++j){
raw_path[j] = a[decomp.vertex_id(i, j)];
}
ntables.emplace_back(raw_path.begin(), raw_path.end());
}
while(q--){
int x, v, w;
cin >> x >> v >> w;
--v; --w;
const auto segs = decomp.shortest_path(v, w);
for(const auto &seg : segs){
const auto &ntable = ntables[seg.path];
if(seg.first < seg.last){
int l = seg.first, r = seg.last;
while(ntable.query(l, r) <= x){
const int p = ntable.query_left(x, l, r);
x %= ntable[p];
}
}else{
int l = seg.last + 1, r = seg.first + 1;
while(ntable.query(l, r) <= x){
const int p = ntable.query_right(x, l, r);
x %= ntable[p];
}
}
}
cout << x << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
J - MODクエリ |
User |
logicmachine |
Language |
C++11 (GCC 4.9.2) |
Score |
400 |
Code Size |
8764 Byte |
Status |
AC |
Exec Time |
1218 ms |
Memory |
25368 KB |
Judge Result
Set Name |
Small |
All |
Score / Max Score |
30 / 30 |
370 / 370 |
Status |
|
|
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 |
51 ms |
940 KB |
15_path_00.txt |
AC |
55 ms |
1048 KB |
15_path_01.txt |
AC |
53 ms |
944 KB |
15_path_02.txt |
AC |
27 ms |
912 KB |
15_path_03.txt |
AC |
27 ms |
916 KB |
15_path_04.txt |
AC |
27 ms |
916 KB |
16_path_05.txt |
AC |
29 ms |
908 KB |
16_path_06.txt |
AC |
29 ms |
992 KB |
16_path_07.txt |
AC |
27 ms |
1004 KB |
16_path_08.txt |
AC |
27 ms |
912 KB |
16_path_09.txt |
AC |
28 ms |
916 KB |
17_path_10.txt |
AC |
1155 ms |
9324 KB |
17_path_11.txt |
AC |
1208 ms |
9332 KB |
17_path_12.txt |
AC |
1218 ms |
9332 KB |
17_path_13.txt |
AC |
1217 ms |
9332 KB |
17_path_14.txt |
AC |
1168 ms |
9344 KB |
20_random_15.txt |
AC |
29 ms |
980 KB |
20_random_16.txt |
AC |
27 ms |
868 KB |
20_random_17.txt |
AC |
27 ms |
912 KB |
21_random_18.txt |
AC |
28 ms |
944 KB |
21_random_19.txt |
AC |
29 ms |
916 KB |
21_random_20.txt |
AC |
28 ms |
876 KB |
30_random_21.txt |
AC |
27 ms |
936 KB |
30_random_22.txt |
AC |
28 ms |
864 KB |
30_random_23.txt |
AC |
28 ms |
920 KB |
40_random_24.txt |
AC |
985 ms |
17500 KB |
40_random_25.txt |
AC |
997 ms |
17576 KB |
40_random_26.txt |
AC |
928 ms |
17560 KB |
49_sample_02.txt |
AC |
28 ms |
940 KB |
61_test_27.txt |
AC |
790 ms |
15464 KB |
61_test_28.txt |
AC |
740 ms |
15488 KB |
61_test_29.txt |
AC |
744 ms |
15476 KB |
63_star_30.txt |
AC |
776 ms |
25364 KB |
63_star_31.txt |
AC |
629 ms |
25344 KB |
63_star_32.txt |
AC |
716 ms |
25368 KB |
64_three_33.txt |
AC |
1042 ms |
9160 KB |
64_three_34.txt |
AC |
1127 ms |
10008 KB |
64_three_35.txt |
AC |
1090 ms |
9324 KB |