Submission #2967536
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back
const ll INF = (1LL<<60);
const int MOD = 1000000007;
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.first<<','<<a.second<<')';
return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
out<<'[';
REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
out<<']';
return out;
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
// Binary Indexed Tree
// 0-indexed
template <typename T>
class BIT {
private:
// データ
vector<T> bit;
// 単位元, 要素数
int neutral = 0;
// 更新クエリ, 区間クエリ
function<T(T,T)> f = [](const T l, const T r) -> T { return l+r; },
g = [](const T l, const T r) -> T { return l+r; };
public:
// 初期化
BIT(int n_ = 1e5) { init(n_); }
void init(int n_ = 1e5) { bit.assign(n_+1, neutral); }
// iに対する点更新クエリ
void update(int i, T w) {
for(int x = i+1; x < bit.size(); x += x&-x) bit[x] = f(bit[x], w);
}
// [0,i)に対する区間クエリ
T query(int i) {
T ret = neutral;
for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
return ret;
}
};
template <typename S>
class sparseTable {
public:
using T = typename S::T;
int n;
vector<int> log2;
vector<vector<T>> t;
sparseTable(int nn = 1e5) { init(nn); }
void init(int nn) {
n = nn;
log2.assign(n+1, 0);
for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
t.assign(log2[n]+1, vector<T>(n));
}
void build(vector<T> v) {
for(int i=0; i<n; ++i) t[0][i] = v[i];
for(int j=1; j<=log2[n]; ++j) {
int w = 1LL<<(j-1);
for (int i = 0; i+(w<<1) <= n; ++i) {
t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
}
}
}
// [l, r]
T query(int l, int r) {
int j = log2[r - l];
return S::op(t[j][l], t[j][r-(1 << j)+1]);
}
};
struct minimum {
using T = PII;
static T op(const T& a, const T& b) { return min(a, b); }
};
struct LCA {
struct edge { int id, to, cost; };
const int n = 0;
const int log2_n = 0;
VVI par;
vector<vector<edge>> g;
VI depth; // 頂点iの深さ
VI vs; // 頂点を訪問順に並べたもの
VI depth_seq; // depth_seq[i] = (頂点vs[i]の深さ)
VI id; // 頂点が初めてvsに登場するインデックス
VI es; // 辺のインデックス(i*2+(葉方向:0,根方向:1))
VI w; // 辺の重み
BIT<int> bit;
sparseTable<minimum> st;
void dfs(int v, int p, int d, int &k) {
id[v] = k; vs[k] = v; depth_seq[k++] = d; depth[v] = d;
for(auto e: g[v]) {
if(e.to == p) continue;
bit.update(k, e.cost); es[e.id*2] = k;
dfs(e.to, v, d+1, k);
vs[k] = v; depth_seq[k++] = d;
bit.update(k, -e.cost); es[e.id*2+1] = k;
}
}
LCA(int n_=1e5) :
n(n_), g(n, vector<edge>()), depth(n), vs(2*n-1),
depth_seq(2*n-1), id(n), es((n-1)*2), w(n-1)
{
bit.init(2*n-1);
}
// u-vに重みcostのi番目の辺を張る
void add_edge(int i, int u, int v, int cost) {
g[u].PB({i, v, cost});
g[v].PB({i, u, cost});
w[i] = cost;
}
// rootを根として初期化
void build(int root = 0) {
int k = 0;
dfs(root, -1, 0, k);
// RMQの初期化
vector<PII> v(2*n-1);
REP(i, 2*n-1) v[i] = {depth_seq[i], i};
st.init(2*n-1);
st.build(v);
}
// uとvのlcaを返す O(logN)
int get(int u, int v) {
if(id[u] > id[v]) swap(u, v);
return vs[st.query(id[u], id[v]).second];
}
// uとvの距離を返す O(logN)
int length(int u, int v) {
int lca = get(u, v);
return bit.query(id[v]) + bit.query(id[u]) - 2*bit.query(id[lca]);
}
// 辺xのコストをtに変更 O(logN)
void update(int x, int t) {
t = !w[x];
bit.update(es[x*2], t - w[x]);
bit.update(es[x*2+1], w[x] - t);
w[x] = t;
}
};
int c[100010];
signed main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
LCA lca(n);
VI p(n);
FOR(i, 1, n) {
cin >> p[i]; p[i]--;
}
REP(i, n) cin >> c[i];
FOR(i, 1, n) {
int cost = c[i]==c[p[i]]?1:0;
lca.add_edge(i-1, i, p[i], cost);
}
lca.build();
vector<string> ans;
int q;
cin >> q;
REP(i, q) {
int type;
cin >> type;
if(type == 1) {
int u; cin >> u; u--;
if(u == 0) continue;
// u と p[u] の間の辺について更新
lca.update(u-1, 0);
} else {
int u, v; cin >> u >> v; u--, v--;
ans.PB(lca.length(u,v)>=1?"NO":"YES");
}
}
REP(i, ans.size()) {
cout << ans[i] << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
H - 白黒ツリー |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
5361 Byte |
Status |
AC |
Exec Time |
313 ms |
Memory |
119492 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04 |
All |
00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_graph_random_color_random_query_random_00, 01_graph_random_color_random_query_random_01, 01_graph_random_color_random_query_random_02, 01_graph_random_color_random_query_random_03, 01_graph_random_color_random_query_random_04, 01_graph_random_color_random_query_random_05, 01_graph_random_color_random_query_random_06, 01_graph_random_color_random_query_random_07, 01_graph_random_color_random_query_random_08, 01_graph_random_color_random_query_random_09, 02_graph_random_color_same_query_random_00, 02_graph_random_color_same_query_random_01, 02_graph_random_color_same_query_random_02, 02_graph_random_color_same_query_random_03, 02_graph_random_color_same_query_random_04, 02_graph_random_color_same_query_random_05, 02_graph_random_color_same_query_random_06, 02_graph_random_color_same_query_random_07, 02_graph_random_color_same_query_random_08, 02_graph_random_color_same_query_random_09, 03_graph_random_color_alternate_query_random_00, 03_graph_random_color_alternate_query_random_01, 03_graph_random_color_alternate_query_random_02, 03_graph_random_color_alternate_query_random_03, 03_graph_random_color_alternate_query_random_04, 03_graph_random_color_alternate_query_random_05, 03_graph_random_color_alternate_query_random_06, 03_graph_random_color_alternate_query_random_07, 03_graph_random_color_alternate_query_random_08, 03_graph_random_color_alternate_query_random_09, 10_graph_path_color_alternate_query_all2_00, 10_graph_path_color_random_query_random_00, 10_graph_path_color_random_query_random_01, 10_graph_path_color_random_query_random_02, 10_graph_path_color_random_query_random_03, 10_graph_path_color_random_query_random_04, 10_graph_path_color_random_query_random_05, 10_graph_path_color_same_query_all2_00, 10_graph_path_color_sametoAlternate_query_11...12_00, 20_graph_star_color_alternate_query_all2_00, 20_graph_star_color_random_query_1Center2random_00, 20_graph_star_color_random_query_1Center2random_01, 20_graph_star_color_random_query_1Center2random_02, 20_graph_star_color_random_query_1Center2random_03, 20_graph_star_color_random_query_1Center2random_04, 20_graph_star_color_random_query_1Center2random_05, 20_graph_star_color_random_query_1Center2random_06, 20_graph_star_color_random_query_1Center2random_07, 20_graph_star_color_random_query_1Center2random_08, 20_graph_star_color_random_query_1Center2random_09, 20_graph_star_color_random_query_1Center2random_10, 20_graph_star_color_random_query_random_00, 20_graph_star_color_random_query_random_01, 20_graph_star_color_random_query_random_02, 20_graph_star_color_random_query_random_03, 20_graph_star_color_random_query_random_04, 20_graph_star_color_random_query_random_05, 20_graph_star_color_same_query_all2_00, 20_graph_star_color_sametoAlternate_query_11...12_00, 30_graph_hitode_color_random_query_random_00, 30_graph_hitode_color_random_query_random_01, 30_graph_hitode_color_random_query_random_02, 30_graph_hitode_color_random_query_random_03, 30_graph_hitode_color_random_query_random_04, 30_graph_hitode_color_random_query_random_05, 40_graph_caterpillar_color_random_query_random_00, 40_graph_caterpillar_color_random_query_random_01, 40_graph_caterpillar_color_random_query_random_02, 40_graph_caterpillar_color_random_query_random_03, 40_graph_caterpillar_color_random_query_random_04, 40_graph_caterpillar_color_random_query_random_05, 50_graph_binaryTree_color_random_query_random_00, 50_graph_binaryTree_color_random_query_random_01, 50_graph_binaryTree_color_random_query_random_02, 50_graph_binaryTree_color_random_query_random_03, 50_graph_binaryTree_color_random_query_random_04, 50_graph_binaryTree_color_random_query_random_05, 60_graph_ternaryTree_color_random_query_random_00, 60_graph_ternaryTree_color_random_query_random_01, 60_graph_ternaryTree_color_random_query_random_02, 60_graph_ternaryTree_color_random_query_random_03, 60_graph_ternaryTree_color_random_query_random_04, 60_graph_ternaryTree_color_random_query_random_05, 70_graph_triangle_color_random_query_random_00, 70_graph_triangle_color_random_query_random_01, 70_graph_triangle_color_random_query_random_02, 70_graph_triangle_color_random_query_random_03, 70_graph_triangle_color_random_query_random_04, 70_graph_triangle_color_random_query_random_05 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
15 ms |
29952 KB |
00_sample_01 |
AC |
15 ms |
29952 KB |
00_sample_02 |
AC |
15 ms |
29952 KB |
00_sample_03 |
AC |
15 ms |
29952 KB |
00_sample_04 |
AC |
15 ms |
29952 KB |
01_graph_random_color_random_query_random_00 |
AC |
56 ms |
35428 KB |
01_graph_random_color_random_query_random_01 |
AC |
42 ms |
35172 KB |
01_graph_random_color_random_query_random_02 |
AC |
29 ms |
31076 KB |
01_graph_random_color_random_query_random_03 |
AC |
30 ms |
31972 KB |
01_graph_random_color_random_query_random_04 |
AC |
38 ms |
31460 KB |
01_graph_random_color_random_query_random_05 |
AC |
43 ms |
30976 KB |
01_graph_random_color_random_query_random_06 |
AC |
48 ms |
33252 KB |
01_graph_random_color_random_query_random_07 |
AC |
108 ms |
107844 KB |
01_graph_random_color_random_query_random_08 |
AC |
77 ms |
47236 KB |
01_graph_random_color_random_query_random_09 |
AC |
91 ms |
83652 KB |
02_graph_random_color_same_query_random_00 |
AC |
47 ms |
32996 KB |
02_graph_random_color_same_query_random_01 |
AC |
130 ms |
105028 KB |
02_graph_random_color_same_query_random_02 |
AC |
42 ms |
35812 KB |
02_graph_random_color_same_query_random_03 |
AC |
148 ms |
32044 KB |
02_graph_random_color_same_query_random_04 |
AC |
84 ms |
37220 KB |
02_graph_random_color_same_query_random_05 |
AC |
92 ms |
51972 KB |
02_graph_random_color_same_query_random_06 |
AC |
30 ms |
31204 KB |
02_graph_random_color_same_query_random_07 |
AC |
90 ms |
35556 KB |
02_graph_random_color_same_query_random_08 |
AC |
39 ms |
34276 KB |
02_graph_random_color_same_query_random_09 |
AC |
31 ms |
31332 KB |
03_graph_random_color_alternate_query_random_00 |
AC |
28 ms |
32228 KB |
03_graph_random_color_alternate_query_random_01 |
AC |
90 ms |
105796 KB |
03_graph_random_color_alternate_query_random_02 |
AC |
34 ms |
34916 KB |
03_graph_random_color_alternate_query_random_03 |
AC |
58 ms |
37348 KB |
03_graph_random_color_alternate_query_random_04 |
AC |
48 ms |
38756 KB |
03_graph_random_color_alternate_query_random_05 |
AC |
83 ms |
95300 KB |
03_graph_random_color_alternate_query_random_06 |
AC |
118 ms |
114756 KB |
03_graph_random_color_alternate_query_random_07 |
AC |
56 ms |
35300 KB |
03_graph_random_color_alternate_query_random_08 |
AC |
121 ms |
102596 KB |
03_graph_random_color_alternate_query_random_09 |
AC |
102 ms |
54404 KB |
10_graph_path_color_alternate_query_all2_00 |
AC |
292 ms |
119492 KB |
10_graph_path_color_random_query_random_00 |
AC |
259 ms |
119492 KB |
10_graph_path_color_random_query_random_01 |
AC |
124 ms |
119492 KB |
10_graph_path_color_random_query_random_02 |
AC |
118 ms |
119492 KB |
10_graph_path_color_random_query_random_03 |
AC |
118 ms |
119492 KB |
10_graph_path_color_random_query_random_04 |
AC |
117 ms |
119492 KB |
10_graph_path_color_random_query_random_05 |
AC |
118 ms |
119492 KB |
10_graph_path_color_same_query_all2_00 |
AC |
284 ms |
119492 KB |
10_graph_path_color_sametoAlternate_query_11...12_00 |
AC |
109 ms |
119492 KB |
20_graph_star_color_alternate_query_all2_00 |
AC |
280 ms |
109508 KB |
20_graph_star_color_random_query_1Center2random_00 |
AC |
282 ms |
110020 KB |
20_graph_star_color_random_query_1Center2random_01 |
AC |
265 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_02 |
AC |
247 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_03 |
AC |
226 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_04 |
AC |
210 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_05 |
AC |
195 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_06 |
AC |
177 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_07 |
AC |
157 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_08 |
AC |
137 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_09 |
AC |
119 ms |
109380 KB |
20_graph_star_color_random_query_1Center2random_10 |
AC |
100 ms |
109380 KB |
20_graph_star_color_random_query_random_00 |
AC |
212 ms |
109380 KB |
20_graph_star_color_random_query_random_01 |
AC |
123 ms |
109636 KB |
20_graph_star_color_random_query_random_02 |
AC |
109 ms |
110148 KB |
20_graph_star_color_random_query_random_03 |
AC |
109 ms |
109380 KB |
20_graph_star_color_random_query_random_04 |
AC |
108 ms |
109380 KB |
20_graph_star_color_random_query_random_05 |
AC |
108 ms |
109380 KB |
20_graph_star_color_same_query_all2_00 |
AC |
279 ms |
109380 KB |
20_graph_star_color_sametoAlternate_query_11...12_00 |
AC |
101 ms |
109380 KB |
30_graph_hitode_color_random_query_random_00 |
AC |
313 ms |
113348 KB |
30_graph_hitode_color_random_query_random_01 |
AC |
159 ms |
113348 KB |
30_graph_hitode_color_random_query_random_02 |
AC |
149 ms |
113348 KB |
30_graph_hitode_color_random_query_random_03 |
AC |
144 ms |
113348 KB |
30_graph_hitode_color_random_query_random_04 |
AC |
151 ms |
113348 KB |
30_graph_hitode_color_random_query_random_05 |
AC |
147 ms |
113348 KB |
40_graph_caterpillar_color_random_query_random_00 |
AC |
236 ms |
109892 KB |
40_graph_caterpillar_color_random_query_random_01 |
AC |
122 ms |
109892 KB |
40_graph_caterpillar_color_random_query_random_02 |
AC |
109 ms |
109892 KB |
40_graph_caterpillar_color_random_query_random_03 |
AC |
110 ms |
109892 KB |
40_graph_caterpillar_color_random_query_random_04 |
AC |
110 ms |
109892 KB |
40_graph_caterpillar_color_random_query_random_05 |
AC |
110 ms |
109892 KB |
50_graph_binaryTree_color_random_query_random_00 |
AC |
264 ms |
111044 KB |
50_graph_binaryTree_color_random_query_random_01 |
AC |
161 ms |
111044 KB |
50_graph_binaryTree_color_random_query_random_02 |
AC |
141 ms |
111044 KB |
50_graph_binaryTree_color_random_query_random_03 |
AC |
139 ms |
111044 KB |
50_graph_binaryTree_color_random_query_random_04 |
AC |
141 ms |
111044 KB |
50_graph_binaryTree_color_random_query_random_05 |
AC |
142 ms |
111044 KB |
60_graph_ternaryTree_color_random_query_random_00 |
AC |
155 ms |
109252 KB |
60_graph_ternaryTree_color_random_query_random_01 |
AC |
145 ms |
109252 KB |
60_graph_ternaryTree_color_random_query_random_02 |
AC |
137 ms |
109252 KB |
60_graph_ternaryTree_color_random_query_random_03 |
AC |
135 ms |
109252 KB |
60_graph_ternaryTree_color_random_query_random_04 |
AC |
135 ms |
109252 KB |
60_graph_ternaryTree_color_random_query_random_05 |
AC |
135 ms |
109252 KB |
70_graph_triangle_color_random_query_random_00 |
AC |
276 ms |
110148 KB |
70_graph_triangle_color_random_query_random_01 |
AC |
142 ms |
110148 KB |
70_graph_triangle_color_random_query_random_02 |
AC |
143 ms |
110148 KB |
70_graph_triangle_color_random_query_random_03 |
AC |
141 ms |
110148 KB |
70_graph_triangle_color_random_query_random_04 |
AC |
143 ms |
110148 KB |
70_graph_triangle_color_random_query_random_05 |
AC |
140 ms |
110148 KB |