Submission #1711906
Source Code Expand
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
class LowestCommonAncestor {
public:
ll vmax, lmax, *depth, **parent;
vector<ll> *edge;
LowestCommonAncestor(ll vmax): vmax(vmax) {
ll p = 1;
for(lmax = 0; p < vmax; lmax++) p *= 2;
edge = new vector<ll>[vmax];
depth = new ll[vmax];
parent = new ll*[lmax];
REP(i, 0, lmax) parent[i] = new ll[vmax];
}
void init(ll root) {
dfs(root, -1, 0);
REP(i, 0, lmax - 1) REP(j, 0, vmax) {
parent[i + 1][j] = parent[i][j] >= 0 ? parent[i][parent[i][j]] : -1;
}
}
ll query(ll u, ll v) {
if(depth[u] > depth[v]) swap(u, v);
REP(i, 0, lmax) if(((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];
if(u == v) return u;
for(ll i = lmax - 1; i >= 0; i--) if(parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
return parent[0][u];
}
private:
void dfs(ll v, ll p, ll d) {
parent[0][v] = p;
depth[v] = d;
REP(i, 0, edge[v].size()) if(edge[v][i] != p) dfs(edge[v][i], v, d + 1);
}
};
template<typename T> class SegmentTree {
vector<T> vec;
ll n;
T e;
T (*op)(T, T);
public:
SegmentTree(ll _n, T _e, T (*_op)(T, T)) : n(1), e(_e), op(_op) {
while(n < _n) n *= 2;
vec.resize(n * 2 - 1, e);
}
T query(ll a, ll b) { return rquery(a, b, 0, 0, n); }
void update(ll a, T k) {
a += n - 1;
vec[a] = k;
while(a > 0) {
a = (a - 1) / 2;
vec[a] = op(vec[a * 2 + 1], vec[a * 2 + 2]);
}
}
private:
T rquery(ll a, ll b, ll k, ll l, ll r) {
if(r <= a || b <= l) return e;
if(a <= l && r <= b) return vec[k];
T vl = rquery(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = rquery(a, b, k * 2 + 2, (l + r) / 2, r);
return op(vl, vr);
}
};
ll N, A, B, Q, M, K, V[100000];
vector<ll> E[100000];
pll euler[100000];
void dfs(ll v, ll p, ll &cnt) {
euler[v].first = cnt;
for(ll u : E[v]) if(u != p) dfs(u, v, cnt);
euler[v].second = cnt++;
}
int main(void) {
scanf("%lld", &N);
REP(i, 0, N - 1) {
scanf("%lld %lld", &A, &B);
A--;
B--;
E[A].push_back(B);
E[B].push_back(A);
}
ll cnt = 0;
dfs(0, -1, cnt);
LowestCommonAncestor lca(N);
REP(v, 0, N) for(ll u : E[v]) lca.edge[v].push_back(u);
lca.init(0);
SegmentTree<ll> segtree(N, 0, [](ll a, ll b) { return a + b; });
scanf("%lld", &Q);
while(Q--) {
scanf("%lld %lld", &M, &K);
REP(i, 0, M) {
scanf("%lld", &V[i]);
V[i]--;
}
vector<pll> order(M);
REP(i, 0, M) order[i] = pll(euler[V[i]].second, V[i]);
sort(order.begin(), order.end());
vector<ll> vec(M * 2 - 1);
REP(i, 0, M) vec[i] = V[i];
REP(i, 0, M - 1) {
ll p = order[i + 0].second;
ll q = order[i + 1].second;
vec[M + i] = lca.query(p, q);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
ll ans = 0;
REP(i, 0, M) segtree.update(euler[V[i]].second, 1);
REP(i, 0, vec.size()) {
ll s = segtree.query(euler[vec[i]].first, euler[vec[i]].second + 1);
if(s >= K) ans = max(ans, lca.depth[vec[i]]);
}
printf("%lld\n", ans);
REP(i, 0, M) segtree.update(euler[V[i]].second, 0);
}
}
Submission Info
Submission Time |
|
Task |
F - 根付き木のみさわさん |
User |
kshinya |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3447 Byte |
Status |
RE |
Exec Time |
193 ms |
Memory |
37504 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:91:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &N);
^
./Main.cpp:93:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &A, &B);
^
./Main.cpp:109:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &Q);
^
./Main.cpp:111:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &M, &K);
^
./Main.cpp:113:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &V[i]);
...
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
0 / 20 |
0 / 110 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt |
Subtask2 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_15.txt, subtask_02_16.txt, subtask_02_17.txt, subtask_02_18.txt, subtask_02_19.txt, subtask_02_20.txt, subtask_02_21.txt, subtask_02_22.txt, subtask_02_23.txt, subtask_02_24.txt, subtask_02_25.txt, subtask_02_26.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
2688 KB |
sample_02.txt |
AC |
2 ms |
2816 KB |
sample_03.txt |
AC |
2 ms |
2816 KB |
subtask_01_01.txt |
RE |
102 ms |
2688 KB |
subtask_01_02.txt |
AC |
2 ms |
2688 KB |
subtask_01_03.txt |
AC |
3 ms |
2816 KB |
subtask_01_04.txt |
AC |
3 ms |
2816 KB |
subtask_01_05.txt |
AC |
17 ms |
2816 KB |
subtask_01_06.txt |
AC |
2 ms |
2816 KB |
subtask_01_07.txt |
AC |
3 ms |
2816 KB |
subtask_01_08.txt |
AC |
14 ms |
2816 KB |
subtask_01_09.txt |
AC |
2 ms |
2816 KB |
subtask_01_10.txt |
AC |
3 ms |
2816 KB |
subtask_01_11.txt |
AC |
13 ms |
2816 KB |
subtask_01_12.txt |
AC |
2 ms |
2816 KB |
subtask_01_13.txt |
AC |
3 ms |
2816 KB |
subtask_01_14.txt |
AC |
13 ms |
2816 KB |
subtask_01_15.txt |
AC |
2 ms |
2816 KB |
subtask_01_16.txt |
AC |
4 ms |
2816 KB |
subtask_01_17.txt |
AC |
15 ms |
2816 KB |
subtask_01_18.txt |
AC |
2 ms |
2816 KB |
subtask_01_19.txt |
AC |
3 ms |
2816 KB |
subtask_01_20.txt |
AC |
13 ms |
2816 KB |
subtask_01_21.txt |
AC |
2 ms |
2816 KB |
subtask_01_22.txt |
AC |
3 ms |
2816 KB |
subtask_01_23.txt |
AC |
15 ms |
2816 KB |
subtask_01_24.txt |
AC |
2 ms |
2816 KB |
subtask_01_25.txt |
AC |
3 ms |
2816 KB |
subtask_01_26.txt |
AC |
14 ms |
2816 KB |
subtask_02_01.txt |
AC |
142 ms |
34432 KB |
subtask_02_02.txt |
AC |
167 ms |
31360 KB |
subtask_02_03.txt |
AC |
178 ms |
31104 KB |
subtask_02_04.txt |
AC |
132 ms |
35328 KB |
subtask_02_05.txt |
AC |
144 ms |
32012 KB |
subtask_02_06.txt |
AC |
151 ms |
31696 KB |
subtask_02_07.txt |
AC |
130 ms |
35200 KB |
subtask_02_08.txt |
AC |
132 ms |
32880 KB |
subtask_02_09.txt |
AC |
147 ms |
31900 KB |
subtask_02_10.txt |
AC |
133 ms |
33280 KB |
subtask_02_11.txt |
AC |
138 ms |
30188 KB |
subtask_02_12.txt |
AC |
155 ms |
29948 KB |
subtask_02_13.txt |
AC |
164 ms |
34048 KB |
subtask_02_14.txt |
AC |
185 ms |
31936 KB |
subtask_02_15.txt |
AC |
180 ms |
30940 KB |
subtask_02_16.txt |
AC |
130 ms |
37504 KB |
subtask_02_17.txt |
AC |
126 ms |
34848 KB |
subtask_02_18.txt |
AC |
159 ms |
33920 KB |
subtask_02_19.txt |
AC |
171 ms |
34048 KB |
subtask_02_20.txt |
AC |
186 ms |
31472 KB |
subtask_02_21.txt |
AC |
193 ms |
30736 KB |
subtask_02_22.txt |
AC |
149 ms |
35840 KB |
subtask_02_23.txt |
AC |
149 ms |
35356 KB |
subtask_02_24.txt |
AC |
157 ms |
31940 KB |
subtask_02_25.txt |
AC |
148 ms |
30592 KB |
subtask_02_26.txt |
AC |
142 ms |
34304 KB |