Submission #863648

#	Time	Username	Problem	Language	Result	Execution time	Memory
863648		nnhzzz	Birthday gift (IZhO18_treearray)	C++14	100 / 100	795 ms	89412 KiB

treearray

// cre: Nguyen Ngoc Hung - Train VOI 2024

#include<bits/stdc++.h>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define               gcd  __gcd
#define                fi  first
#define                se  second
#define                ll  long long
#define               ull  unsigned long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define        REP(i,a,b)  for(int i = (a); i<=(b); ++i)
#define       REPD(i,a,b)  for(int i = (a); i>=(b); --i)
#define   REPDIS(i,a,b,c)  for(int i = (a); i<=(b); i+=c)
#define              endl  "\n"
// #define               int  ll

//-------------------------------------------------------------//
const int oo = 1e9,LOG = 18,MAXN = 2e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T> bool mini(T &a, const T &b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, const T &b){if(a<b){a=b;return true;}return false;}

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int a[MAXN],b[MAXN],dep[MAXN],f[MAXN][LOG];
set<int> s1[MAXN],s2[MAXN];
vi adj[MAXN];

void dfs(int u, int par){
    REP(i,1,LOG-1) f[u][i] = f[f[u][i-1]][i-1];
    for(auto v:adj[u]){
        if(v==par) continue;
        f[v][0] = u;
        dep[v] = dep[u]+1;
        dfs(v,u);
    }
}

int lca(int u, int v){
    if(dep[u]>dep[v]) swap(u,v);
    int dis = dep[v]-dep[u];
    REPD(i,LOG-1,0){
        if(BIT(dis,i)){
            v = f[v][i];
        }
    }
    if(u==v) return u;
    REPD(i,LOG-1,0){
        if(f[u][i]!=f[v][i]){
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

void ans(int i, int j){
    cout << i << " " << j << "\n";
}

void solve(){
    int n,m,q; cin >> n >> m >> q;
    REP(i,2,n){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    REP(i,1,m){
        cin >> a[i];
        s2[a[i]].insert(i);
    }
    REP(i,1,m-1){
        b[i] = lca(a[i],a[i+1]);
        s1[b[i]].insert(i);
    }
    while(q--){
        int t; cin >> t;
        if(t==1){
            int pos,val; cin >> pos >> val;
            s2[a[pos]].erase(pos);
            if(pos<m){
                int x = lca(val,a[pos+1]);
                s1[b[pos]].erase(pos);
                b[pos] = x;
                s1[b[pos]].insert(pos);
            }
            if(pos>1){
                int x = lca(a[pos-1],val);
                s1[b[pos-1]].erase(pos-1);
                b[pos-1] = x;
                s1[b[pos-1]].insert(pos-1);
            }
            a[pos] = val;
            s2[a[pos]].insert(pos);
        }else{
            int l,r,x; cin >> l >> r >> x;
            if(l==r){
                if(a[l]==x) ans(l,l);
                else ans(-1,-1);
                continue;
            }
            auto it = s1[x].lower_bound(l);
            if(it!=s1[x].end() && *it<r){
                ans(*it,*it+1);
                continue;
            }
            auto it1 = s2[x].lower_bound(l);
            // cout << "waring: " << x << " ";
            if(it1!=s2[x].end() && *it1<=r) ans(*it1,*it1);
            else ans(-1,-1);
        }
    }
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define name "test"
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    #define name1 "nnhzzz"
    if(fopen(name1".inp","r")){
        freopen(name1".inp","r",stdin);
        freopen(name1".out","w",stdout);
    }
    int test = 1;
    while(test--){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(name1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44