| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 884112 |
2023-12-06T15:58:44 Z |
fanwen |
Tourism (JOI23_tourism) |
C++17 |
|
6 ms |
12892 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define clog if(false) cerr
#endif
template <class T> struct Fenwick_Tree {
vector<T> bit;
int n;
Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
void clear() { fill(bit.begin(), bit.end(), T(0)); }
void update(int u, T val) {
for (; u <= n; u += u & -u) bit[u] += val;
}
T get(int u) {
T ans = 0;
for (; u; u -= u & -u) ans += bit[u];
return ans;
}
T get(int l, int r) {
return get(r) - get(l - 1);
}
};
const int MAX = 1e5 + 5;
int n, m, q, c[MAX], ans[MAX], local[MAX], depth[MAX], header[MAX], par[MAX];
int numChild[MAX];
vector <int> adj[MAX];
vector <pair <int, int>> queries[MAX];
void dfs(int u, int p) {
numChild[u] = 1;
int Max = 0, id = 0;
for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != p) {
int v = adj[u][i];
dfs(v, u);
numChild[u] += numChild[v];
if(Max < numChild[v]) {
Max = numChild[v];
id = i;
}
}
swap(adj[u][0], adj[u][id]);
}
void dfs_hld(int u, int p) {
static int run = 0;
local[u] = ++run;
par[u] = p;
for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != p) {
int v = adj[u][i];
if(i == 0 && numChild[v] * 2 >= numChild[u]) {
header[u] = header[p], depth[u]= depth[p];
} else {
header[u] = u;
depth[u] = depth[p] + 1;
}
dfs_hld(v, u);
}
}
int it[4 * MAX];
Fenwick_Tree <int> bit;
void pushdown(int idx) {
if(it[idx] == -1) return;
it[idx << 1] = it[idx << 1 | 1] = it[idx];
}
void update(int idx, int l, int r, int u, int v, int val) {
if(l > v || r < u) return;
if(l >= u && r <= v && it[idx] >= 0) {
if(it[idx] > 0) bit.update(it[idx], - (r - l + 1));
bit.update(it[idx] = val, r - l + 1);
return;
}
pushdown(idx);
int mid = l + r >> 1;
update(idx << 1, l, mid, u, v, val);
update(idx << 1 | 1, mid + 1, r, u, v, val);
it[idx] = (it[idx << 1] == it[idx << 1 | 1] ? it[idx << 1] : -1);
}
void update_hld(int u, int v, int val) {
while(header[u] != header[v]) {
if(local[header[u]] < local[header[v]]) swap(u, v);
update(1, 1, n, local[header[u]], local[u], val);
u = par[header[u]];
}
update(1, 1, n, min(local[u], local[v]), max(local[u], local[v]), val);
}
void you_make_it(void) {
cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= m; ++i) cin >> c[i];
dfs(1, 0); depth[1] = header[1] = 1; dfs_hld(1, 0);
fill(ans + 1, ans + q + 1, 1);
for (int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
if(l < r) queries[l].emplace_back(r, i);
}
bit = Fenwick_Tree <int> (n);
for (int i = m - 1; i >= 1; --i) {
update_hld(c[i], c[i + 1], i + 1);
for (auto [r, id] : queries[i]) ans[id] = bit.get(r);
}
for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
file("tourism");
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message
tourism.cpp: In function 'void update(int, int, int, int, int, int)':
tourism.cpp:95:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int mid = l + r >> 1;
| ~~^~~
tourism.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(int) [with T = int]':
tourism.cpp:78:20: required from here
tourism.cpp:17:9: warning: 'Fenwick_Tree<int>::n' will be initialized after [-Wreorder]
17 | int n;
| ^
tourism.cpp:16:15: warning: 'std::vector<int> Fenwick_Tree<int>::bit' [-Wreorder]
16 | vector<T> bit;
| ^~~
tourism.cpp:18:5: warning: when initialized here [-Wreorder]
18 | Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
| ^~~~~~~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:140:5: note: in expansion of macro 'file'
140 | file("tourism");
| ^~~~
tourism.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:140:5: note: in expansion of macro 'file'
140 | file("tourism");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Runtime error |
6 ms |
12892 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
