# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
793735 |
2023-07-26T06:04:36 Z |
vjudge1 |
Tourism (JOI23_tourism) |
C++17 |
|
134 ms |
12784 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int M = (1 << 18);
// segment Sum + update in pos
int segSum[2 * M];
void update(int pos, int val) {
for(segSum[pos += M] += val; pos > 1; pos >>= 1) {
segSum[pos >> 1] = segSum[pos] + segSum[(pos ^ 1)];
}
}
int get(int ql, int qr) {
int res = 0;
for(ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
if(ql & 1) res += segSum[ql++];
if(qr & 1) res += segSum[--qr];
}
return res;
}
template<typename T>
struct SprarseTable {
int len;
vector<vector<T>> st;
T (*F) (T, T);
void init(vector<T> &a, T (*f)(T, T)) {
F = f;
len = (int)a.size();
int mxpw = 32 - __builtin_clz(len);
st.resize(mxpw);
st[0] = a;
for(int k = 1; k < mxpw; k++) {
st[k].resize(len - (1 << k) + 1);
for(int i = 0; i < (int)st[k].size(); i++) {
st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
}
T get(int l, int r) {
int mxpw = 31 - __builtin_clz(r - l + 1);
return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
}
};
int n, m, q;
vector<int> g[N];
vector<pair<int, int>> e;
int sm[N];
int tin[N], tout[N], anc[N][17], depth[N], T;
void calc(int s, int p) {
for(int to : g[s]) {
if(to == p) continue;
calc(to, s);
sm[s] += sm[to];
}
}
void precalc(int s, int p) {
tin[s] = T++;
anc[s][0] = p;
for(int i = 1; i < 17; i++)
anc[s][i] = anc[anc[s][i - 1]][i - 1];
for(int to : g[s]) {
if(to == p) continue;
depth[to] = depth[s] + 1;
precalc(to, s);
}
tout[s] = T++;
}
struct query {
int l, r, i;
};
int curAns;
void add(int ver) {
if(get(tin[ver], tout[ver]) == 0) curAns++;
int u = ver;
for(int i = 16; i >= 0; i--) {
if(get(tin[ anc[u][i] ], tout[ anc[u][i] ]) == 0)
u = anc[u][i];
}
curAns += depth[ver] - depth[u];
update(tin[ver], +1);
}
void del(int ver) {
update(tin[ver], -1);
int u = ver;
for(int i = 16; i >= 0; i--) {
if(get(tin[ anc[u][i] ], tout[ anc[u][i] ]) == 0)
u = anc[u][i];
}
curAns -= depth[ver] - depth[u];
if(get(tin[ver], tout[ver]) == 0) curAns--;
}
vector<query> qr;
int ans[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
for(int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
e.push_back({u, v});
}
vector<int> ver(m + 1);
for(int i = 1; i <= m; i++)
cin >> ver[i];
// if(n <= 2000 && q <= 2000 && m <= 2000) {
// while(q --> 0) {
// int l, r;
// cin >> l >> r;
// for(int i = l; i <= r; i++)
// sm[ver[i]]++;
// calc(1, 1);
// int res = 1;
// for(int i = 1; i <= n; i++) {
// res += (sm[i] && sm[i] < r - l + 1);
// sm[i] = 0;
// }
// cout << res << '\n';
// }
// return 0;
// }
// bool subtask = 1;
// for(int i = 0; i < n - 1; i++) {
// if(e[i].first != i + 1 || e[i].second != i + 2)
// subtask = 0;
// }
precalc(1, 1);
/*
if(subtask) {
vector<int> ti(m + 1);
for(int i = 1; i <= m; i++)
ti[i] = depth[ver[i]];
SprarseTable<int> mn, mx;
mn.init(ti, [](int a, int b) {return (a < b ? a : b);});
mx.init(ti, [](int a, int b) {return (a > b ? a : b);});
while(q --> 0) {
int l, r;
cin >> l >> r;
cout << mx.get(l, r) - mn.get(l, r) + 1 << '\n';
}
return 0;
}
*/
for(int i = 0; i < q; i++) {
query c;
cin >> c.l >> c.r; c.i = i;
qr.push_back(c);
}
// sort(qr.begin(), qr.end(), [](query a, query b) {return (a.l < b.l);});
int curL = 1, curR = 0;
for(query c : qr) {
while(curR < c.r) {
add(ver[++curR]);
}
while(curL < c.l) {
del(ver[curL++]);
}
ans[c.i] = curAns;
}
for(int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2680 KB |
Output is correct |
2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2680 KB |
Output is correct |
2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Incorrect |
108 ms |
10296 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2724 KB |
Output is correct |
3 |
Correct |
2 ms |
2772 KB |
Output is correct |
4 |
Incorrect |
134 ms |
12784 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2680 KB |
Output is correct |
2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |