oj.uz

Submission #944908

# Submission time Handle Problem Language Result Execution time Memory
944908 2024-03-13T07:52:43 Z phoenix0423 Tourism (JOI23_tourism) C++17
5 / 100
 2419 ms 59428 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0);
#pragma GCC optimize("Ofast","unroll-loops")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 3e5 + 5;
const int INF = 1e9 + 7;
int n, m, q;
vector<int> adj[maxn];
int dep[maxn], in[maxn], dfn = 0;
int arr[maxn][18];
int id[maxn];

void dfs(int pos, int prev){
    in[pos] = ++dfn;
    id[dfn] = pos;
    arr[dfn][0] = dep[pos];
    for(auto x : adj[pos]){
        if(x == prev) continue;
        dep[x] = dep[pos] + 1;
        dfs(x, pos);
        arr[++dfn][0] = dep[pos];
    }
    arr[++dfn][0] = dep[pos];
}

int lca(int a, int b){
    if(a > b) swap(a, b);
    int len = __lg(b - a + 1);
    return min(arr[a][len], arr[b - (1 << len) + 1][len]);
}

struct info{
    int l, r, id;
    info(){}
    info(int _l, int _r, int _id) : l(_l), r(_r), id(_id){}
    bool operator < (const info& other) const{
        return r < other.r;
    };
};
vector<info> b[500];
const int block = 320;
int ans[maxn];
int c[maxn], loc[maxn];
int cur = 0;
int path(int a, int b){
    return dep[a] + dep[b] - 2 * lca(in[a], in[b]);
}
struct node{
    int l, r, val;
} st[maxn];

struct rollback{
    int l, r, m;
};
stack<rollback> stk;
void roll_back(){
    auto [l, r, m] = stk.top(); stk.pop();
    cur -= path(st[l].val, st[r].val);
    cur += path(st[l].val, st[m].val) + path(st[m].val, st[r].val);
    st[l].r = m, st[r].l = m;
}
void del(int x){
    x = loc[x];
    int prv = st[x].l, nxt = st[x].r;
    stk.push({prv, nxt, x});
    cur -= path(st[prv].val, st[x].val) + path(st[x].val, st[nxt].val);
    cur += path(st[prv].val, st[nxt].val);
    st[prv].r = nxt, st[nxt].l = prv;
}

signed main(void){
    fastio;
    cin>>n>>m>>q;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(0, 0);
    for(int i = 1; (1 << i) <= dfn; i++){
        for(int j = 0; j + (1 << i) - 1 <= dfn; j++){
            arr[j][i] = min(arr[j][i - 1], arr[j + (1 << (i - 1))][i - 1]);
        }
    }
    for(int i = 0; i < m; i++) cin>>c[i], c[i] --;
    for(int i = 0; i < q; i++){
        int l, r;
        cin>>l>>r;
        l--, r--;
        b[l / block].pb(info(l, r, i));
    }
    for(int i = 0; i <= m / block; i++){
        sort(b[i].begin(), b[i].end());
    }
    vector<pll> cpy;
    for(int i = 0; i < m; i++) cpy.eb(c[i], i);
    sort(cpy.begin(), cpy.end(), [&](pll a, pll b){ return in[a.f] < in[b.f];});
    for(int i = 0; i < m; i++){
        auto [val, id] = cpy[i];
        loc[id] = i;
        st[i].val = val;
        if(!i) st[i].l = m - 1;
        else st[i].l = i - 1;
        if(i == m - 1) st[i].r = 0;
        else st[i].r = i + 1;
    }
    for(int i = 0; i < m; i++) cur += path(st[i].val, st[st[i].r].val);
    int cl = 0, cr = m - 1;
    for(int i = 0; i <= m / block; i++){
        if(!b[i].size()) continue;
        for(auto [l, r, id] : b[i]){
            while(r > cr){
                roll_back();
                cr++;
            }
            while(r < cr){
                del(cr--);
            }
            while(cl < l) del(cl++);
            ans[id] = cur;
            while(cl > i * block){
                roll_back();
                cl--;
            }
        }
    }
    for(int i = 0; i < q; i++) cout<<ans[i] / 2 + 1<<"\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19288 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 3 ms 19388 KB Output is correct
4 Correct 4 ms 19292 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 4 ms 19292 KB Output is correct
8 Correct 4 ms 19288 KB Output is correct
9 Correct 5 ms 19288 KB Output is correct
10 Correct 5 ms 19292 KB Output is correct
11 Correct 5 ms 19292 KB Output is correct
12 Correct 4 ms 19288 KB Output is correct
13 Correct 4 ms 19532 KB Output is correct
14 Correct 4 ms 19292 KB Output is correct
15 Correct 5 ms 19788 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 7 ms 19292 KB Output is correct
19 Correct 4 ms 19292 KB Output is correct
20 Correct 5 ms 19288 KB Output is correct
21 Correct 4 ms 19292 KB Output is correct
22 Correct 4 ms 19292 KB Output is correct
23 Correct 4 ms 19292 KB Output is correct
24 Correct 5 ms 19292 KB Output is correct
25 Correct 4 ms 19292 KB Output is correct
26 Correct 5 ms 19292 KB Output is correct
27 Correct 4 ms 19508 KB Output is correct
28 Correct 4 ms 19292 KB Output is correct
29 Correct 5 ms 19292 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19288 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 3 ms 19388 KB Output is correct
4 Correct 4 ms 19292 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 4 ms 19292 KB Output is correct
8 Correct 4 ms 19288 KB Output is correct
9 Correct 5 ms 19288 KB Output is correct
10 Correct 5 ms 19292 KB Output is correct
11 Correct 5 ms 19292 KB Output is correct
12 Correct 4 ms 19288 KB Output is correct
13 Correct 4 ms 19532 KB Output is correct
14 Correct 4 ms 19292 KB Output is correct
15 Correct 5 ms 19788 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 7 ms 19292 KB Output is correct
19 Correct 4 ms 19292 KB Output is correct
20 Correct 5 ms 19288 KB Output is correct
21 Correct 4 ms 19292 KB Output is correct
22 Correct 4 ms 19292 KB Output is correct
23 Correct 4 ms 19292 KB Output is correct
24 Correct 5 ms 19292 KB Output is correct
25 Correct 4 ms 19292 KB Output is correct
26 Correct 5 ms 19292 KB Output is correct
27 Correct 4 ms 19508 KB Output is correct
28 Correct 4 ms 19292 KB Output is correct
29 Correct 5 ms 19292 KB Output is correct
30 Incorrect 13 ms 21596 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19744 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 14 ms 19676 KB Output is correct
4 Incorrect 1885 ms 59428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19292 KB Output is correct
2 Incorrect 77 ms 51424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19292 KB Output is correct
2 Correct 4 ms 19288 KB Output is correct
3 Correct 14 ms 19548 KB Output is correct
4 Incorrect 2419 ms 56584 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19288 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 3 ms 19388 KB Output is correct
4 Correct 4 ms 19292 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct
6 Correct 4 ms 19292 KB Output is correct
7 Correct 4 ms 19292 KB Output is correct
8 Correct 4 ms 19288 KB Output is correct
9 Correct 5 ms 19288 KB Output is correct
10 Correct 5 ms 19292 KB Output is correct
11 Correct 5 ms 19292 KB Output is correct
12 Correct 4 ms 19288 KB Output is correct
13 Correct 4 ms 19532 KB Output is correct
14 Correct 4 ms 19292 KB Output is correct
15 Correct 5 ms 19788 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 7 ms 19292 KB Output is correct
19 Correct 4 ms 19292 KB Output is correct
20 Correct 5 ms 19288 KB Output is correct
21 Correct 4 ms 19292 KB Output is correct
22 Correct 4 ms 19292 KB Output is correct
23 Correct 4 ms 19292 KB Output is correct
24 Correct 5 ms 19292 KB Output is correct
25 Correct 4 ms 19292 KB Output is correct
26 Correct 5 ms 19292 KB Output is correct
27 Correct 4 ms 19508 KB Output is correct
28 Correct 4 ms 19292 KB Output is correct
29 Correct 5 ms 19292 KB Output is correct
30 Incorrect 13 ms 21596 KB Output isn't correct
31 Halted 0 ms 0 KB -