Submission #831308

#	Time	Username	Problem	Language	Result	Execution time	Memory
831308		Cookie	Tourism (JOI23_tourism)	C++14	100 / 100	879 ms	22628 KiB

tourism

#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);
                    
                }
                
                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 (stderr)

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:140:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |         for(auto [r, id]: queries[i]){
      |                  ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41