제출 #502652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502652		LucaIlie	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1681 ms	126500 KiB

treearray

#include <iostream>
#include <vector>
#include <set>
 
#define MAX_N 200000
#define MAX_M 200000
#define MAX_LG2N 18
 
using namespace std;
 
struct nodEuler {
    int nod, depth;
 
    bool operator < (const nodEuler &a) const {
        return depth < a.depth;
    }
};
 
struct solutie {
    int lca, left, right;
 
    bool operator < (const solutie &a) const {
        if ( lca == a.lca ) {
            if ( left == a.left )
                return right < a.right;
            return left < a.left;
        }
        return lca < a.lca;
    }
};
 
int eulerSize;
int poz[MAX_N], lg2[2 * MAX_N + 1], v[MAX_M];
nodEuler euler[2 * MAX_N], rmq[2 * MAX_N][MAX_LG2N + 1];
vector <int> muchii[MAX_N];
set <solutie> s;
 
void dfs( int parent, int nod, int depth ) {
    int i;
 
    euler[eulerSize] = { nod, depth };
    poz[nod] = eulerSize;
    eulerSize++;
    for ( i = 0; i < muchii[nod].size(); i++ ) {
        if ( muchii[nod][i] != parent ) {
            dfs( nod, muchii[nod][i], depth + 1 );
            euler[eulerSize] = { nod, depth };
            poz[nod] = eulerSize;
            eulerSize++;
        }
    }
}
 
void initLCA() {
    int i, j;
 
    dfs( -1, 0, 0 );
 
    for ( i = 0; i < eulerSize; i++ )
        rmq[i][0] = euler[i];
    for ( j = 1; (1 << j) <= eulerSize; j++ ) {
        for ( i = 0; i + (1 << j) <= eulerSize; i++ ) {
            if ( rmq[i][j - 1] < rmq[i + (1 << (j - 1))][j - 1] )
                rmq[i][j] = rmq[i][j - 1];
            else
                rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
        }
    }
 
    for ( i = 2; i <= eulerSize; i++ )
        lg2[i] = lg2[i / 2] + 1;
}
 
int queryLCA( int x, int y ) {
    int s, d, aux, j;
 
    s = poz[x];
    d = poz[y];
    if ( s > d ) {
        aux = s;
        s = d;
        d = aux;
    }
 
    j = lg2[d - s + 1] ;
    if ( rmq[s][j] < rmq[d - (1 << j) + 1][j] )
        return rmq[s][j].nod;
    return rmq[d - (1 << j) + 1][j].nod;
};
 
int main() {
    int n, m, q, x, y, tip, l, r, p, i;
 
    cin >> n >> m >> q;
    for ( i = 0; i < n - 1; i++ ) {
        cin >> x >> y;
        x--;
        y--;
 
        muchii[x].push_back( y );
        muchii[y].push_back( x );
    }
 
    initLCA();
 
    for ( i = 0; i < m; i++ ) {
        cin >> v[i];
        v[i]--;
 
        s.insert( { v[i], i, i } );
        if( i > 0 )
            s.insert( { queryLCA( v[i - 1], v[i] ), i - 1, i } );
    }
 
    for ( i = 0; i < q; i++ ) {
        cin >> tip;
 
        if ( tip == 1 ) {
            cin >> p >> x;
            p--;
            x--;
 
            s.erase( { v[p], p, p } );
            if ( p > 0 )
                s.erase( { queryLCA( v[p - 1], v[p] ), p - 1, p } );
            if ( p < m - 1 )
                s.erase( { queryLCA( v[p], v[p + 1] ), p, p + 1 } );
 
            v[p] = x;
 
            s.insert( { v[p], p, p } );
            if ( p > 0 )
                s.insert( { queryLCA( v[p - 1], v[p] ), p - 1, p } );
            if ( p < m - 1 )
                s.insert( { queryLCA( v[p], v[p + 1] ), p, p + 1 } );
        } else {
            cin >> l >> r >> x;
            l--;
            r--;
            x--;
 
            auto it = s.lower_bound( { x, l, 0 } );
            if ( it != s.end() && it->lca == x && it->left >= l && it->right <= r )
                cout << it->left + 1 << " " << it->right + 1 << "\n";
            else
                cout << "-1 -1\n";
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'void dfs(int, int, int)':
treearray.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for ( i = 0; i < muchii[nod].size(); i++ ) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~

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