제출 #1363430

#제출 시각아이디문제언어결과실행 시간메모리
1363430sophiaeternaliaTourists (EGOI22_tourists)C++20
50 / 100
4091 ms37700 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int int64_t

vector<pair<int, int>> o;
vector<int> h;
vector<vector<int>> p, g;
int in;

bool pa(int pp, int c){
    if (o[pp].first<=o[c].first and o[c].second<=o[pp].second){
        return true;
    }
    return false;
}

int lca(int v, int u, int ind){
    if (v==u){
        return u;
    }
    if (h[v]>h[u]){
        swap(v, u);
    }
    if (pa(v, u)){
        return v;
    }
    int pv=p[v][0];
    if (pa(pv, u)){
        return pv;
    }
    while (ind>=p[v].size()){
        ind=p[v].size()-1;
    }
    while (pa(p[v][ind], u)){
        ind--;
    }
    return lca(p[v][ind], u, ind);
}

void dfs(int v, int la){
    if (la!=-1){
        h[v]=h[la]+1;
    }
    o[v].first=in++;
    p[v].push_back(la);
    while (p[p[v][p[v].size()-1]].size()>=p[v].size()){
        int a=p[v].size();
        p[v].push_back(p[p[v][a]][a]);
    }
    for (auto u: g[v]){
        if (u!=la){
            dfs(u, v);
        }
    }
    o[v].second=in++;
}

signed main(){
    cin.tie(0); ios_base::sync_with_stdio(NULL);

    int n, m, q;
    cin>>n>>m>>q;
    vector<int> po(m), sc(m, 0);
    for (int i=0; i<m; i++){
        int a;
        cin>>a;
        a--;
        po[i]=a;
    }
    in=0;
    o.resize(n);
    h.assign(n, 0);
    p.resize(n);
    g.resize(n);
    for (int i=0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    int mind=100;
    for (int i=0; i<q; i++){
        //cout<<i<<endl;
        char c;
        cin>>c;
        if (c=='t'){
            int x, y, z;
            cin>>x>>y>>z;
            x--;
            y--;
            z--;
            for (int j=x; j<=y; j++){
                int an=lca(po[j], z, mind);
                sc[j]-=h[po[j]]+h[z]-2*h[an];
                po[j]=z;
            }
        } else if (c=='e'){
            int x, y;
            cin>>x>>y;
            x--;
            for (int j=0; j<m; j++){
                if (po[j]==x){
                    sc[j]+=y;
                }
            }
        } else {
            //cout<<'a'<<endl;
            int x;
            cin>>x;
            x--;
            cout<<sc[x]<<"\n";
        }
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…