Submission #535121
Source Code Expand
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <limits>
#include <ctime>
#include <cassert>
#include <map>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <stack>
#include <queue>
#include <numeric>
#include <iterator>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
#include <unordered_map>
#include <unordered_set>
class HL_decomposition {
public:
const vector<vector<int>>& e;
const int n;
vector<int> par, depth, ord; //親,深さ、トポロジカルソート
vector<int> cluster; //decompositionした結果どのクラスタに属するか
vector<vector<int> > pathes; //各クラスタの、上から下へのパス
vector<int> path_idx; // path_idx[v] = 上記パスでのindex
void init(int v) {
depth.resize(n, 0);
par.resize(n, 0);
ord.resize(n, 0);
depth[v] = 0;
par[v] = -1;
ord[0] = v; //ordをキューとして使い、bfsする
for (int p = 0, r = 1; p < r; p++) {
int cur = ord[p];
for (int nv : e[cur]) {
if (nv == par[cur]) continue;
ord[r++] = nv;
par[nv] = cur;
depth[nv] = depth[cur] + 1;
}
}
}
void decomposition() {
vector<int> subtree_size(n, 1);
for (int i = n - 1; i > 0; i--) subtree_size[par[ord[i]]] += subtree_size[ord[i]];
cluster.resize(n, -1);
int cluster_type = 0;
FOR(i, n) {
int u = ord[i];
if (cluster[u] == -1) cluster[u] = cluster_type++;
int max_subsize = -1, selected = -1;
for (int v : e[u]) {
if (par[u] != v && max_subsize < subtree_size[v]) {
max_subsize = subtree_size[v];
selected = v;
}
}
if (selected != -1) cluster[selected] = cluster[u];
}
}
void enum_pathes() {
int cluster_num = 0;
vector<int> rp(n);
FOR(i, n) {
rp[cluster[i]]++;
cluster_num = max(cluster_num, cluster[i]);
}
cluster_num++;
pathes.resize(cluster_num);
FOR(i, cluster_num) pathes[i].resize(rp[i]);
for (int i = n - 1; i >= 0; i--) {
int u = ord[i];
pathes[cluster[u]][--rp[cluster[u]]] = u;
}
}
void set_path_idx() {
path_idx.resize(n);
for (const vector<int>& path : pathes) {
FOR(i, sz(path)) path_idx[path[i]] = i;
}
}
public:
HL_decomposition(const vector<vector<int>>& e) : e(e), n(sz(e)) {
init(0);
decomposition();
enum_pathes();
set_path_idx();
}
};
const int INF = ten(9) + 10;
struct Pgreater {
vector<int> v;
static Pgreater zero() {
Pgreater ret;
return ret;
}
bool is_zero() const { return sz(v) == 0; }
Pgreater operator+(const Pgreater& r) const {
if (is_zero()) return r;
else if (r.is_zero()) return *this;
Pgreater ret;
ret.v = v;
for (auto x : r.v) if(ret.v.back() > x) ret.v.push_back(x);
return ret;
}
int lower_max(int val) {
int l = -1, r = sz(v);
while (r - l != 1) {
int md = (l + r) / 2;
if (val < v[md]) l = md;
else r = md;
}
if (r == sz(v)) return INF;
return v[r];
}
int query(int val) {
while (true) {
int mod = lower_max(val);
if (mod == INF) return val;
val %= mod;
}
}
};
struct Plesser {
vector<int> v;
static Plesser zero() {
Plesser ret;
return ret;
}
bool is_zero() const { return sz(v) == 0; }
Plesser operator + (const Plesser& r) const {
if (is_zero()) return r;
else if (r.is_zero()) return *this;
Plesser ret;
FOR(i, sz(v)) {
if (v[i] < r.v[0]) ret.v.push_back(v[i]);
}
for (auto x : r.v) ret.v.push_back(x);
return ret;
}
int lower_max(int val) {
int l = -1, r = sz(v);
while (r - l != 1) {
int md = (l + r) / 2;
if (val < v[md]) r = md;
else l = md;
}
if (l == -1) return INF;
return v[l];
}
int query(int val) {
while (true) {
int mod = lower_max(val);
if (mod == INF) return val;
val %= mod;
}
}
};
//0-indexed segment tree
template<class T>
class seg_tree {
public:
vector<T> dat;
int n;
bool dir;
void propagate(int i) {
dat[i] = dat[i * 2 + 1] + dat[i * 2 + 2];
}
seg_tree(vector<int>& d,bool dir) : dir(dir) {
n = 1;
while (n < sz(d)) n <<= 1;
dat.resize(2 * n - 1);
fill(dat.begin(), dat.end(), T::zero());
for (int i = 0; i < sz(d); i++) dat[n - 1 + i].v.push_back(d[i]);
for (int i = n - 2; i >= 0; i--) propagate(i);
}
//[a,b)
int query(int a, int b, int val) {
return query(a, b, val, 0, 0, n);
}
int query(int a, int b, int val, int k, int l, int r) {
if (r <= a || b <= l) return val;
if (a <= l && r <= b) return dat[k].query(val);
int md = (l + r) / 2; //[l,md),[md,r)
int nl = k * 2 + 1, nr = nl + 1;
if (dir) {
val = query(a, b, val, nl, l, md);
val = query(a, b, val, nr, md, r);
} else {
val = query(a, b, val, nr, md, r);
val = query(a, b, val, nl, l, md);
}
return val;
}
};
class LCA {
public:
vector<vector<int>>& e;
int V, logV;
vector<int> depth;
vector<vector<int> > parent;
LCA(vector<vector<int>>& e) : e(e) {
this->V = sz(e);
logV = 0;
while (V >= (1 << logV)) logV++;
this->depth = vector<int>(V);
this->parent = vector<vector<int> >(logV, vector<int>(V));
dfs(0, -1, 0);
build();
}
void dfs(int v, int par, int d) {
depth[v] = d;
parent[0][v] = par;
for (auto to : e[v]) {
if (par == to) continue;
dfs(to, v, d + 1);
}
}
void build() {
for (int k = 0; k + 1 < logV; k++) {
for (int v = 0; v < V; v++) {
if (parent[k][v] < 0) parent[k + 1][v] = -1;
else parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
int prev_parent(int u, int par) {
for (int k = logV - 1; k >= 0; k--) {
int diff = depth[u] - depth[par];
if ((diff - (1 << k)) > 0) {
u = parent[k][u];
}
}
return u;
}
int query(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int k = 0; k < logV; k++) {
if ((depth[v] - depth[u]) >> k & 1)
v = parent[k][v];
}
if (u == v) return u;
for (int k = logV - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
};
class tree_query {
LCA* lca;
HL_decomposition *hl;
vector<pair<seg_tree<Plesser>*, seg_tree<Pgreater>*>> rmqs;
public:
tree_query(vector<vector<int>>& e, vector<int>& a) {
lca = new LCA(e);
hl = new HL_decomposition(e);
rmqs.resize(sz(hl->pathes));
FOR(i, sz(rmqs)) {
vector<int> vals;
for (auto x : hl->pathes[i]) vals.push_back(a[x]);
rmqs[i].first = new seg_tree<Plesser>(vals, false);
rmqs[i].second = new seg_tree<Pgreater>(vals, true);
}
}
// u -- v を u -- lca(u,v) , v - lca(u,v)の子 に分ける
pair<Pii, Pii> expose(int u, int v) {
auto l = lca->query(u, v);
int l2 = -1;
if (l != v) l2 = lca->prev_parent(v, l);
return make_pair(Pii(u, l), Pii(v, l2));
}
int query_core(int u, int par, int val, bool dir_par) {
if (par == -1) return val;
vector<tuple<int, int, int>> qv;
while (true) {
int l_index = 0;
if (hl->cluster[u] == hl->cluster[par]) l_index = hl->path_idx[par];
qv.emplace_back(u, l_index, hl->path_idx[u] + 1);
if (hl->cluster[u] == hl->cluster[par]) break;
u = hl->par[hl->pathes[hl->cluster[u]][0]];
}
if (dir_par) {
for (auto ulr : qv) {
int u, l, r; tie(u, l, r) = ulr;
val = rmqs[hl->cluster[u]].first->query(l, r, val);
}
} else {
reverse(qv.begin(), qv.end());
for (auto ulr : qv) {
int u, l, r; tie(u, l, r) = ulr;
val = rmqs[hl->cluster[u]].second->query(l, r, val);
}
}
return val;
}
int query(int u, int v, int val) {
auto ep = expose(u, v);
val = query_core(ep.first.first, ep.first.second, val, true);
val = query_core(ep.second.first, ep.second.second, val, false);
return val;
}
~tree_query() {
delete lca;
delete hl;
FOR(i, sz(rmqs)) delete rmqs[i].first , delete rmqs[i].second;
}
};
vector<int> solve_naive(vector<int> a, vector<tuple<int, int, int>> query) {
vector<int> ans;
for (auto& xvw : query) {
int x, v, w; tie(x, v, w) = xvw;
for (int i = v; i <= w; i++) {
x %= a[i];
}
ans.push_back(x);
}
return ans;
}
vector<int> solve2(vector<int> a, vector<tuple<int, int, int>> query) {
vector<int> ans;
seg_tree<Pgreater> seg(a, true);
for (auto& xvw : query) {
int x, v, w; tie(x, v, w) = xvw;
x = seg.query(v, w + 1, x);
ans.push_back(x);
}
return ans;
}
void test() {
int n = 5, q = 10;
vector<int> a;
FOR(i, 10) a.push_back(rand() % 30 + 1);
vector<tuple<int, int, int>> query;
FOR(i, q) {
int x, u, v;
x = rand();
u = rand() % n;
v = rand() % n;
if (u == v) u--;
if (u == -1) u++, v++;
if (u > v) swap(u, v);
query.emplace_back(x, u, v);
}
auto a1 = solve_naive(a, query);
auto a2 = solve2(a, query);
if (a1 != a2) {
FOR(i, n) {
printf("%d ",a[i]);
}
puts("");
FOR(i, sz(a1)) if (a1[i] != a2[i]) {
int x, u, v; tie(x, u, v) = query[i];
printf("%d %d %d\n", x, u, v);
}
return;
}
}
int main() {
//FOR(_, 100) {
// test();
//}
int n, q; reader(n, q);
vector<int> v(n);
FOR(i, n) reader(v[i]);
vector<vector<int>> e(n);
FOR(i, n - 1) {
int a, b; scanf("%d%d", &a, &b);
a--; b--;
e[a].push_back(b);
e[b].push_back(a);
}
tree_query tq(e, v);
FOR(i, q) {
int x, v, w; reader(x, v, w);
v--; w--;
int ret = tq.query(v, w, x);
writerLn(ret);
}
}
Submission Info
Submission Time
2015-10-24 17:46:15+0900
Task
J - MODクエリ
User
math
Language
C++11 (GCC 4.9.2)
Score
400
Code Size
12185 Byte
Status
AC
Exec Time
722 ms
Memory
49164 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:454:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
^
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
29 ms
748 KB
15_path_00.txt
AC
28 ms
796 KB
15_path_01.txt
AC
25 ms
932 KB
15_path_02.txt
AC
26 ms
924 KB
15_path_03.txt
AC
26 ms
800 KB
15_path_04.txt
AC
26 ms
796 KB
16_path_05.txt
AC
26 ms
800 KB
16_path_06.txt
AC
26 ms
920 KB
16_path_07.txt
AC
26 ms
916 KB
16_path_08.txt
AC
26 ms
800 KB
16_path_09.txt
AC
25 ms
920 KB
17_path_10.txt
AC
596 ms
44180 KB
17_path_11.txt
AC
632 ms
44192 KB
17_path_12.txt
AC
612 ms
44176 KB
17_path_13.txt
AC
586 ms
44184 KB
17_path_14.txt
AC
586 ms
44188 KB
20_random_15.txt
AC
26 ms
916 KB
20_random_16.txt
AC
26 ms
920 KB
20_random_17.txt
AC
26 ms
920 KB
21_random_18.txt
AC
26 ms
788 KB
21_random_19.txt
AC
26 ms
920 KB
21_random_20.txt
AC
26 ms
792 KB
30_random_21.txt
AC
26 ms
812 KB
30_random_22.txt
AC
26 ms
800 KB
30_random_23.txt
AC
26 ms
800 KB
40_random_24.txt
AC
693 ms
43160 KB
40_random_25.txt
AC
722 ms
43280 KB
40_random_26.txt
AC
697 ms
43288 KB
49_sample_02.txt
AC
25 ms
928 KB
61_test_27.txt
AC
714 ms
43932 KB
61_test_28.txt
AC
695 ms
43804 KB
61_test_29.txt
AC
696 ms
43036 KB
63_star_30.txt
AC
437 ms
44948 KB
63_star_31.txt
AC
445 ms
44944 KB
63_star_32.txt
AC
426 ms
44944 KB
64_three_33.txt
AC
636 ms
43544 KB
64_three_34.txt
AC
630 ms
49164 KB
64_three_35.txt
AC
670 ms
45592 KB