This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int abs(int x) {
if(x < 0) return -x;
return x;
}
const int LOG = 17;
const int OFF = 1 << LOG;
const int INF = 1e9;
struct intv {
int l, r, val;
bool op;
intv (int l, int r, int val) : l(l), r(r), val(val) { op = 0; }
intv (int l, int r, int val, int op) : l(l), r(r), val(val), op(op) {}
bool operator< (intv a) const { return l < a.l || (l == a.l && r < a.r); }
};
int CNT;
int head[OFF], heav[OFF], pos[OFF], par[OFF], dep[OFF];
vector<int> g[OFF];
vector<intv> ups;
int dfs(int u) {
int siz = 1, maxs = 0, ind = 0;
for(int v : g[u]) {
if(v == par[u]) continue;
par[v] = u, dep[v] = dep[u] + 1;
int res = dfs(v);
if(res > maxs) maxs = res, ind = v;
siz += res;
}
heav[u] = ind;
// printf("%d -> %d\n", u, ind);
return siz;
}
void decomp(int u, int h) {
pos[u] = CNT++, head[u] = h;
// printf("%d[%d, %d]\n", u, pos[u], head[u]);
if(heav[u] && u != 1) decomp(heav[u], h);
for(int v : g[u]) {
if(v == par[u] || v == heav[u] && u != 1) continue;
decomp(v, v);
}
}
int fen[OFF];
set<intv> s;
void add(int x, int val) {
for(x; x < OFF; x += x & -x) fen[x] += val;
}
int sum(int x) {
int ret = 0;
for(x; x; x -= x & -x) ret += fen[x];
return ret;
}
void change(intv i) {
// if(i.op) printf("%d %d -%d\n", i.l, i.r, i.val);
// else printf("%d %d %d\n", i.l, i.r, i.val);
int val = i.r - i.l + 1;
if(i.op) val = -val;
add(i.val + 1, val);
}
void debug() {
for(auto it : s) {
printf("[%d, %d (%d)] ", it.l, it.r, it.val);
}
printf("\n");
}
//shit
void interval(int l, int r, int val) {
if(l > r) return;
ups.clear();
ups.pb(intv(l, r, val));
auto it = prev(s.upper_bound(intv(l, INF, INF)));
if(it->l < l) ups.pb(intv(it->l, l - 1, it->val));
while(it != s.end() && it->l <= r) {
if(it->r > r) ups.pb(intv(r + 1, it->r, it->val));
auto nit = next(it);
change(intv(it->l, it->r, it->val, 1));
s.erase(it);
it = nit;
}
for(intv p : ups) {
s.insert(p);
change(p);
}
//printf("add %d %d %d\n", l, r, val);
// debug();
}
void update(int u, int v, int val) {
for(; head[u] != head[v]; v = par[head[v]]) {
if(dep[head[u]] > dep[head[v]]) swap(u, v);
interval(pos[head[v]], pos[v], val);
}
if(dep[u] > dep[v]) swap(u, v);
interval(pos[u] + 1, pos[v], val);
}
int n, m, t, ans[OFF];
vector<int> c;
vector<pii> q[OFF];
int main() {
scanf("%d%d%d", &n, &m, &t);
for(int i = 0; i < n - 1; i++) {
int a, b;
scanf("%d%d", &a, &b);
g[a].pb(b);
g[b].pb(a);
}
dfs(1);
decomp(1, 1);
change(intv(1, n - 1, 0));
s.insert(intv(1, n - 1, 0));
for(int i = 0; i < m; i++) {
int x;
scanf("%d", &x);
c.pb(x);
}
for(int i = 0; i < t; i++) {
int l, r;
scanf("%d%d", &l, &r);
q[r].pb({l, i});
}
for(int i = 1; i <= m; i++) {
if(i != 1) update(c[i - 2], c[i - 1], i - 1);
for(pii p : q[i]) ans[p.Y] = sum(p.X);
}
for(int i = 0; i < t; i++) printf("%d\n", n - ans[i]);
return 0;
}
Compilation message (stderr)
tourism.cpp: In function 'void decomp(int, int)':
tourism.cpp:55:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
55 | if(v == par[u] || v == heav[u] && u != 1) continue;
| ~~~~~~~~~~~~~^~~~~~~~~
tourism.cpp: In function 'void add(int, int)':
tourism.cpp:64:6: warning: statement has no effect [-Wunused-value]
64 | for(x; x < OFF; x += x & -x) fen[x] += val;
| ^
tourism.cpp: In function 'int sum(int)':
tourism.cpp:69:6: warning: statement has no effect [-Wunused-value]
69 | for(x; x; x -= x & -x) ret += fen[x];
| ^
tourism.cpp: In function 'int main()':
tourism.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | scanf("%d%d%d", &n, &m, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
tourism.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
tourism.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |