oj.uz

답안 #987668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
987668 2024-05-23T10:29:27 Z snpmrnhlol Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 15248 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector <int> e[N];
vector <pair<int,int>> q2[N];
map <int,pair<int,int>> f;
int sub[N];
int top[N];
int st[N],cnt = 0;
int c[N];
int d[N];
int pr[N];
int ans[N];
int st2[N];
int n,m,q;
void dfs(int node, int p){
    sub[node] = 1;
    pr[node] = p;
    if(p == -1){
        d[node] = 0;
    }else{
        d[node] = d[p] + 1;
    }
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i, node);
        sub[node]+=sub[i];
    }
}
void dfs2(int node, int p){
    int mxid = -1;
    for(auto i:e[node]){
        if(i == p)continue;
        if(mxid == -1 || sub[mxid] < sub[i]){
            mxid = i;
        }
    }
    st[node] = cnt++;
    st2[cnt - 1] = node;
    if(mxid != -1){
        top[mxid] = top[node];
        dfs2(mxid, node);
    }
    for(auto i:e[node]){
        if(i == p || i == mxid)continue;
        top[i] = i;
        dfs2(i, node);
    }
}
int v[N];
void add(int u,int w,int id){
    u = st[u];
    w = st[w];
    if(u > w)swap(u,w);
    //cout<<u<<' '<<w<<' '<<id<<"updates\n";
    ///segment override
    while(1){
        auto x = f.lower_bound(u);
        if(x == f.end() || x->first > w){
            break;
        }
        int l = min(x->first,u),r = max(x->second.first,w),id2 = x->second.second;
        f.erase(x);
        if(l < u){
            f[l] = {u - 1,id2};
        }
        if(w < r){
            f[w + 1] = {r,id2};
        }
    }
    auto x = f.lower_bound(u);
    if(x != f.begin() && prev(x)->second.first >= u){
        int l = min(x->first,u),r = max(x->second.first,w),id2 = x->second.second;
        f.erase(x);
        if(l < u){
            f[l] = {u - 1,id2};
        }
        if(w < r){
            f[w + 1] = {r,id2};
        }
    }

    f[u] = {w,id};
}
int get(int pos){
    int r = 0;
    for(auto i:f){
        if(i.second.second >= pos){
            r+=i.second.first - i.first + 1;
        }
        //cout<<i.first<<' '<<i.second.first<<' '<<i.second.second<<'\n';
    }
    //cout<<'\n';
    return r;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i = 0;i < n - 1;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        e[a].push_back(b);
        e[b].push_back(a);
        v[i] = -1;
    }
    v[n - 1] = -1;
    dfs(0, -1);
    top[0] = 0;
    dfs2(0, -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;
        if(l == r){
            ans[i] = 1;
            continue;
        }
        q2[r - 1].push_back({l - 1,i});
    }
    for(int i = 1;i < m;i++){
        ///add
        int u = c[i],w = c[i - 1];
        while(top[u] != top[w]){
            if(d[top[u]] > d[top[w]])swap(u,w);
            //cout<<w<<' '<<top[w]<<' '<<i - 1<<'\n';
            add(w,top[w],i - 1);
            w = pr[top[w]];
        }
        //cout<<u<<' '<<w<<' '<<i - 1<<'\n';
        add(u,w,i - 1);
        ///queries
        for(auto j:q2[i]){
            ans[j.second] = get(j.first);
        }
    }
    for(int i = 0;i < q;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}
/**
7 2 1
1 2
1 3
2 4
2 5
3 6
3 7
4 5
1 2
**/

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Incorrect 3 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Incorrect 3 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Incorrect 782 ms 11512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Execution timed out 5045 ms 15248 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Incorrect 3 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -