oj.uz

답안 #893772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893772 2023-12-27T11:44:40 Z lolismek Tourism (JOI23_tourism) C++14
18 / 100
 861 ms 1048576 KB 
#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <random>
#include <chrono>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ull = unsigned long long;
using ll = long long;

//#define int __int128
//#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound

#define vt vector
#define FOR(a, b) for(int i = (a); ((a) <= (b) ? i <= (b) : i >= (b));((a) <= (b) ? i++ : i--))
#define sz(x) (int)(x).size() // ?

#define YES cout << "YES\n"
#define NO cout << "NO\n"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rangerng(int l, int r){
    return uniform_int_distribution<>(l, r)(rng);
}

////////////////////////////////////////////////////////////////////////////////////

const int NMAX = 2e5; // ?

vt <int> adj[NMAX + 1];
int c[NMAX + 1];
vt <pii> quer[NMAX + 1];

int Ans[NMAX + 1];

int sz[NMAX + 1];
int par[NMAX + 1];
int hvChild[NMAX + 1];

int lvl[NMAX + 1];

void expl(int node, int parent){
    par[node] = parent;
    sz[node] = 1;

    lvl[node] = lvl[parent] + 1;

    int maxi = 0;
    for(int child : adj[node]){
        if(child != parent){
            expl(child, node);
            sz[node] += sz[child];

            if(sz[child] >= maxi){
                maxi = sz[child];
                hvChild[node] = child;
            }
        }
    }
}

int Id = 0;
int id[NMAX + 1];
int head[NMAX + 1];
int last[NMAX + 1];

int Time = 0;
int pos[NMAX + 1];

void hvFirst(int node, int parent){
    pos[node] = ++Time;
    
    if(hvChild[parent] != node){
        id[node] = ++Id;
        head[Id] = node;
    }else{
        id[node] = id[parent];
    }

    last[id[node]] = node;

    if(hvChild[node] != 0){
        hvFirst(hvChild[node], node);
    }

    for(int child : adj[node]){
        if(child != parent && child != hvChild[node]){
            hvFirst(child, node);
        }
    }
}

namespace AIB{
    int n;
    int aib[NMAX + 2];

    void init(int _n){
        n = _n + 1;
        FOR(1, n){
            aib[i] = 0;
        }
    }

    int lsb(int x){
        return x & -x;
    }

    void update(int pos, int val){
        pos++;
        for(int i = pos; i <= n; i += lsb(i)){
            aib[i] += val;
        }
    }

    int query(int pos){
        int ans = 0;
        pos++;
        for(int i = pos; i >= 1; i -= lsb(i)){
            ans += aib[i];
        }
        return ans;
    }
}

set <pair <pii, int>> S;

void setInterval(int l, int r, int x){
    vt <pair <pii, int>> toErase;
    vt <pair <pii, int>> toInsert;
    toInsert.pb({{l, r}, x});

    for(auto it = S.lb({{l, 0}, 0}); it != S.end() && (*it).fr.fr <= r; it++){
        pair <pii, int> obj = (*it);
        toErase.pb(obj);
        if(obj.fr.sc > r){
            pair <pii, int> newObj = {{r + 1, obj.fr.sc}, obj.sc};
            toInsert.pb(newObj);
        }
    }

    auto it = S.lb({{l, 0}, 0});
    if(!S.empty() && it != S.begin()){
        it--;
        pair <pii, int> obj = (*it);
        if(obj.fr.fr < l && obj.fr.sc >= l){
            toErase.pb(obj);
            toInsert.pb({{obj.fr.fr, l - 1}, obj.sc});
            if(obj.fr.sc > r){
                toInsert.pb({{r + 1, obj.fr.sc}, obj.sc});
            }
        }
    }

    for(auto x : toErase){
        if(S.find(x) != S.end()){
            S.erase(x);
        }
        AIB::update(x.sc, -(x.fr.sc - x.fr.fr + 1));
    }

    for(auto x : toInsert){
        S.insert(x);
        AIB::update(x.sc, +(x.fr.sc - x.fr.fr + 1));
    }
}

void update(int a, int b, int x){
    while(id[a] != id[b]){
        if(lvl[head[id[a]]] > lvl[head[id[b]]]){
            setInterval(pos[head[id[a]]], pos[a], x);
            a = par[head[id[a]]];
        }else{
            setInterval(pos[head[id[b]]], pos[b], x);
            b = par[head[id[b]]];
        }
    }
    setInterval(min(pos[a], pos[b]), max(pos[a], pos[b]), x);
}

void solve(){
    int n, m, q;
    cin >> n >> m >> q;

    FOR(1, n - 1){
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    FOR(1, m){
        cin >> c[i];
    }

    FOR(1, q){
        int x, y;
        cin >> x >> y;
        quer[y].pb({x, i});
    }

    expl(1, 0);
    hvFirst(1, 0);

    AIB::init(m);

    FOR(1, Id){
        S.insert({{pos[head[i]], pos[last[i]]}, 0});
        AIB::update(0, pos[last[i]] - pos[head[i]] + 1);
    }

    FOR(1, m){
        if(i > 1){
            update(c[i - 1], c[i], i - 1);
        }
        update(c[i], c[i], i);

        for(pii x : quer[i]){
            Ans[x.sc] += AIB::query(m) - AIB::query(x.fr - 1);
        }
    }

    for(int i = 1; i <= q; i++){
        cout << Ans[i] << '\n';
    }
}       

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    //cin >> T;

    T = 1;

    while(T--){
        solve();
    }

    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Correct 3 ms 14008 KB Output is correct
3 Correct 4 ms 14172 KB Output is correct
4 Correct 4 ms 14172 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 3 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 4 ms 14168 KB Output is correct
9 Correct 4 ms 14168 KB Output is correct
10 Correct 4 ms 14172 KB Output is correct
11 Correct 4 ms 14172 KB Output is correct
12 Correct 4 ms 14172 KB Output is correct
13 Correct 4 ms 14168 KB Output is correct
14 Correct 4 ms 14172 KB Output is correct
15 Correct 5 ms 14580 KB Output is correct
16 Correct 4 ms 14172 KB Output is correct
17 Correct 4 ms 14172 KB Output is correct
18 Correct 4 ms 14172 KB Output is correct
19 Correct 3 ms 14172 KB Output is correct
20 Correct 3 ms 14172 KB Output is correct
21 Correct 3 ms 14172 KB Output is correct
22 Correct 3 ms 14172 KB Output is correct
23 Correct 3 ms 14236 KB Output is correct
24 Correct 4 ms 14172 KB Output is correct
25 Correct 4 ms 14172 KB Output is correct
26 Correct 4 ms 14172 KB Output is correct
27 Runtime error 643 ms 1048576 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Correct 3 ms 14008 KB Output is correct
3 Correct 4 ms 14172 KB Output is correct
4 Correct 4 ms 14172 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 3 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 4 ms 14168 KB Output is correct
9 Correct 4 ms 14168 KB Output is correct
10 Correct 4 ms 14172 KB Output is correct
11 Correct 4 ms 14172 KB Output is correct
12 Correct 4 ms 14172 KB Output is correct
13 Correct 4 ms 14168 KB Output is correct
14 Correct 4 ms 14172 KB Output is correct
15 Correct 5 ms 14580 KB Output is correct
16 Correct 4 ms 14172 KB Output is correct
17 Correct 4 ms 14172 KB Output is correct
18 Correct 4 ms 14172 KB Output is correct
19 Correct 3 ms 14172 KB Output is correct
20 Correct 3 ms 14172 KB Output is correct
21 Correct 3 ms 14172 KB Output is correct
22 Correct 3 ms 14172 KB Output is correct
23 Correct 3 ms 14236 KB Output is correct
24 Correct 4 ms 14172 KB Output is correct
25 Correct 4 ms 14172 KB Output is correct
26 Correct 4 ms 14172 KB Output is correct
27 Runtime error 643 ms 1048576 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Runtime error 586 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14168 KB Output is correct
2 Correct 396 ms 19508 KB Output is correct
3 Correct 629 ms 20068 KB Output is correct
4 Correct 499 ms 20560 KB Output is correct
5 Correct 772 ms 23976 KB Output is correct
6 Correct 799 ms 23860 KB Output is correct
7 Correct 798 ms 23820 KB Output is correct
8 Correct 819 ms 24068 KB Output is correct
9 Correct 778 ms 23632 KB Output is correct
10 Correct 786 ms 23632 KB Output is correct
11 Correct 761 ms 24020 KB Output is correct
12 Correct 782 ms 23856 KB Output is correct
13 Correct 804 ms 24176 KB Output is correct
14 Correct 773 ms 24808 KB Output is correct
15 Correct 861 ms 27152 KB Output is correct
16 Correct 797 ms 24200 KB Output is correct
17 Correct 798 ms 24176 KB Output is correct
18 Correct 748 ms 24144 KB Output is correct
19 Correct 480 ms 19536 KB Output is correct
20 Correct 486 ms 19288 KB Output is correct
21 Correct 476 ms 19236 KB Output is correct
22 Correct 465 ms 19304 KB Output is correct
23 Correct 475 ms 19096 KB Output is correct
24 Correct 468 ms 19772 KB Output is correct
25 Correct 489 ms 19268 KB Output is correct
26 Correct 475 ms 19328 KB Output is correct
27 Correct 460 ms 19092 KB Output is correct
28 Correct 475 ms 19112 KB Output is correct
29 Correct 489 ms 19540 KB Output is correct
30 Correct 478 ms 19488 KB Output is correct
31 Correct 472 ms 19536 KB Output is correct
32 Correct 501 ms 19916 KB Output is correct
33 Correct 511 ms 21052 KB Output is correct
34 Correct 488 ms 22664 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Runtime error 552 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14172 KB Output is correct
2 Correct 3 ms 14008 KB Output is correct
3 Correct 4 ms 14172 KB Output is correct
4 Correct 4 ms 14172 KB Output is correct
5 Correct 4 ms 14172 KB Output is correct
6 Correct 3 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 4 ms 14168 KB Output is correct
9 Correct 4 ms 14168 KB Output is correct
10 Correct 4 ms 14172 KB Output is correct
11 Correct 4 ms 14172 KB Output is correct
12 Correct 4 ms 14172 KB Output is correct
13 Correct 4 ms 14168 KB Output is correct
14 Correct 4 ms 14172 KB Output is correct
15 Correct 5 ms 14580 KB Output is correct
16 Correct 4 ms 14172 KB Output is correct
17 Correct 4 ms 14172 KB Output is correct
18 Correct 4 ms 14172 KB Output is correct
19 Correct 3 ms 14172 KB Output is correct
20 Correct 3 ms 14172 KB Output is correct
21 Correct 3 ms 14172 KB Output is correct
22 Correct 3 ms 14172 KB Output is correct
23 Correct 3 ms 14236 KB Output is correct
24 Correct 4 ms 14172 KB Output is correct
25 Correct 4 ms 14172 KB Output is correct
26 Correct 4 ms 14172 KB Output is correct
27 Runtime error 643 ms 1048576 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -