제출 #889636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889636		vjudge1	Tourism (JOI23_tourism)	C++17	10 / 100	123 ms	32520 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Sp{
    vector <vector<int>> T;
    int _s;
    Sp(auto &a, int s){
        _s = s;
        T.resize(20);
        int n = a.size();
        for ( auto &x: T ){
            x.resize(n);
        }
        T[0] = a;
        for ( auto &u: T[0] ) u *= _s;
        for ( int i = 1; i < 20; i++ ){
            int k = 1 << i - 1;
            for ( int j = 0; j < n; j++ ){
                T[i][j] = min(T[i - 1][j], T[i - 1][min(n - 1, j + k)]);
            }
        }
    }
    int get(int l, int r){
        int lg = __lg(r - l + 1), k = 1 << lg;
        return min(T[lg][l], T[lg][r + k - 1]) * _s;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q; cin >> n >> m >> q;
    vector <vector<int>> G(n);
    bool Qflag = true;
    for ( int i = 1; i < n; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[u].pb(v), G[v].pb(u);
        if ( u + 1 != v ) Qflag = false;
    }
    vector <int> C(m);
    for ( auto &x: C ){
        cin >> x; --x;
    }
    if ( max({n, m, q}) <= 3000 ){
        while ( q-- ){
            int l, r; cin >> l >> r;
            --l, --r;
            int s = r - l + 1;
            vector <int> sub(n), hv(n);
            for ( int i = l; i <= r; i++ ){
                sub[C[i]]++;
                hv[C[i]] = true;
            }
            auto dfs = [&](auto dfs, int u, int p) -> void{
                for ( auto &v: G[u] ){
                    if ( v != p ){
                        dfs(dfs, v, u);
                        sub[u] += sub[v];
                    }
                }
            };
            dfs(dfs, 0, -1);
            int ans = 0;
            auto dfs2 = [&](auto dfs2, int u, int p) -> void{
                bool flag = false, vs = false;
                for ( auto &v: G[u] ){
                    if ( sub[v] ){
                        if ( !vs ) vs = true;
                        else flag = true;
                    }
                }
                if ( hv[u] || flag ) ++ans;
                for ( auto &v: G[u] ){
                    if ( v != p ){
                        sub[u] -= sub[v];
                        sub[v] += sub[u];
                        dfs2(dfs2, v, u);
                        sub[v] -= sub[u];
                        sub[u] += sub[v];
                    }
                }
            };
            dfs2(dfs2, 0, -1);
            cout << ans << ln;
        } exit(0);
    }
    if ( Qflag ){
        Sp mn(C, 1), mx(C, -1);
        while ( q-- ){
            int l, r; cin >> l >> r;
            --l, --r;
            cout << mx.get(l, r) - mn.get(l, r) + 1 << ln;
        }
    }

    cout << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp:34:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   34 |     Sp(auto &a, int s){
      |        ^~~~
tourism.cpp: In function 'int main()':
tourism.cpp:77:17: warning: unused variable 's' [-Wunused-variable]
   77 |             int s = r - l + 1;
      |                 ^
tourism.cpp: In instantiation of 'Sp::Sp(auto:23&, long long int) [with auto:23 = std::vector<long long int>]':
tourism.cpp:117:19:   required from here
tourism.cpp:44:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |             int k = 1 << i - 1;
      |                          ~~^~~

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