Submission #680423

#	Time	Username	Problem	Language	Result	Execution time	Memory
680423		phoenix	Birthday gift (IZhO18_treearray)	C++17	56 / 100	827 ms	77352 KiB

treearray

#include<bits/stdc++.h>

using namespace std;
const int N = 200000 + 100;
int n, m, q;
int anc[ N ][ 19 ];
vector<int> g[ N ];
int tin[ N ], tout[ N ];

int timer;
set<int> dd[ N ], ss[ N ];

void DFS(int s,int p = 1) {
    tin[ s ] = ++timer;
    anc[ s ][ 0 ] = p;
    for(int i = 1;i < 19;i++)
        anc[ s ][ i ] = anc[anc[ s ][i - 1]][i - 1];

    for(int to : g[ s ]) {
        if(to != p)
            DFS(to, s);
    }
    tout[ s ] = ++timer;
}

bool isAncestor(int a, int b) {
    return (tin[ a ] <= tin[ b ] && tout[ a ] >= tout[ b ]);
}
int lca(int a, int b) {
    if(isAncestor(a, b)) return a;
    if(isAncestor(b, a)) return b;
    for(int i = 18;i >= 0;i--)
        if(!isAncestor(anc[ a ][ i ], b))
            a = anc[ a ][ i ];
    return anc[ a ][ 0 ];
}
pair<int,int> f(set<int> &s, int l, int r, int cc) {
    if(l > r || s.empty() || *s.begin() > r || *(--s.end()) < l) return {-1, -1};
    auto it = s.lower_bound( l );
    if(*it > r) return {-1, -1};
    return {*it, *it + cc};
}
int main() {
    ios::sync_with_stdio( 0 );
    cin.tie( 0 );
    cout.tie( 0 );
    cin >> n >> m >> q;
    int a[m + 1], t[ m ];
    for(int i = 1;i < n;i++) {
        int u, v;
        cin >> u >> v;
        g[ u ].push_back( v );
        g[ v ].push_back( u );
    }
    DFS( 1 );
    for(int i = 1;i <= m;i++) {
        cin >> a[ i ];
        ss[ a[ i ] ].insert( i );
    }
    for(int i = 1;i < m;i++) {
        t[ i ] = lca(a[ i ], a[i + 1]);
        dd[ t[ i ] ].insert( i );
    }

    while(q--) {
        int type;
        cin >> type;
        if(type == 1) {
            int pos, v;
            cin >> pos >> v;
            ss[ a[ pos ] ].erase( pos );
            ss[ v ].insert( pos );
            a[ pos ] = v;
            if(pos < n) {
                dd[ t[ pos ] ].erase( pos );
                t[ pos ] = lca(a[ pos ], a[pos + 1]) ;
                dd[ t[ pos ] ].insert( pos );
            }
            if(pos > 1) {
                dd[ t[pos - 1] ].erase(pos - 1);
                t[pos - 1] = lca(a[pos - 1], a[ pos ]);
                dd[ t[pos - 1] ].insert(pos - 1);
            }
        } else {
            int l, r, u;
            cin >> l >> r >> u;
            pair<int,int> res1 = f(ss[ u ], l, r, 0), res2 = f(dd[ u ], l, r - 1, 1);
            if(res1 != make_pair(-1, -1)) cout << res1.first << ' ' << res1.second << '\n';
            else cout << res2.first << ' ' << res2.second << '\n';
        }
    }
}

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