# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
831305 |
2023-08-20T04:28:18 Z |
Cookie |
Tourism (JOI23_tourism) |
C++14 |
|
79 ms |
16092 KB |
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const int mxn = 1e5 + 5;
int n, m, q;
vt<int>adj[mxn + 5];
int sz[mxn + 1], pa[mxn + 1], head[mxn + 1], id[mxn + 1], tin = 0, c[mxn + 1], neg = -69420, inf = 1e9;
int ans[mxn + 1];
struct BIT{
int bit[mxn + 1];
void upd(int p, int v){
while(p <= m){
bit[p] += v; p += p & (-p);
}
}
int get(int p){
int ans = 0;
while(p){
ans += bit[p]; p -= p & (-p);
}
return(ans);
}
};
void dfs(int s, int pre){
sz[s] = 1;
for(auto i: adj[s]){
if(i != pre){
pa[i] = s;
dfs(i, s); sz[s] += sz[i];
}
}
}
void hld(int s, int pre, int group){
head[s] = group; id[s] = ++tin;
int mx = 0, id = -1;
for(auto i: adj[s]){
if(i != pre && sz[i] > mx){
mx = sz[i]; id = i;
}
}
if(!mx)return;
hld(id, s, group);
for(auto i: adj[s]){
if(i != pre && i != id){
hld(i, s, i);
}
}
}
map<int, int>pos;
vt<pii>hld_path(int u, int v){
vt<pii>path;
while(head[u] != head[v]){
if(id[head[u]] < id[head[v]])swap(u, v);
path.pb(make_pair(id[head[u]], id[u]));
u = pa[head[u]];
}
if(id[u] < id[v]){
path.pb(make_pair(id[u], id[v]));
}else{
path.pb(make_pair(id[v], id[u]));
}
return(path);
}
vt<pii>queries[mxn + 1];
BIT bit;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].pb(v); adj[v].pb(u);
}
for(int i = 1; i <= m; i++){
cin >> c[i];
}
for(int i = 0; i < q; i++){
int l, r; cin >> l >> r;
queries[l].pb(make_pair(r, i));
if(l == r)ans[i]++;
}
dfs(1, -1);
hld(1, -1, 1);
pos[-1] = neg; pos[0] = inf; pos[n + 2] = neg;
for(int i = m - 1; i >= 1; i--){
vt<pii>path = hld_path(c[i], c[i + 1]);
for(int j = 0; j < sz(path); j++){
auto [l, r] = path[j];
for(int tmp: {l, r + 1}){
if(pos.count(tmp))continue;
auto it = prev(pos.lower_bound(tmp));
pos[tmp] = (*it).second;
}
while(1){
auto it = pos.lower_bound(l);
int po = (*it).first, val = (*it).second;
if(po == r + 1)break;
auto it2 = next(it);
if(val != inf){
int po2 = (*it2).first;
bit.upd(val, -(po2 - po));
}
pos.erase(it);
}
for(int tmp: {l, r + 1}){
auto it = pos.lower_bound(tmp);
if((*it).second == (*prev(it)).second)pos.erase(it);
}
pos[l] = i;
bit.upd(i, r - l + 1);
}
for(auto [r, id]: queries[i]){
ans[id] += bit.get(r - 1);
}
}
for(int i = 0; i < q; i++){
cout << ans[i] << "\n";
}
return(0);
}
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:112:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
112 | auto [l, r] = path[j];
| ^
tourism.cpp:143:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
143 | for(auto [r, id]: queries[i]){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5028 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5064 KB |
Output is correct |
4 |
Incorrect |
79 ms |
16092 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |