oj.uz

답안 #502616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
502616 2022-01-06T10:49:37 Z LucaIlie Birthday gift (IZhO18_treearray) C++17
0 / 100
 3 ms 5068 KB 
#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 nod < a.nod;
    }
};

struct solutie {
    int lca, left, right;

    bool operator < (const solutie &a) const {
        if ( lca == a.lca ) {
            if ( left == a.lca )
                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 - 1)) < 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 = 1; i <= eulerSize; i++ )
        lg2[i] = (1 << (lg2[i - 1] + 1)) == i ? lg2[i - 1] + 1 : lg2[i - 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->right <= r )
                cout << it->left + 1 << " " << it->right + 1 << "\n";
            else
                cout << -1 << " " << -1 << "\n";
        }
    }
    return 0;
}
/**
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message

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
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB n=5
2 Incorrect 2 ms 5068 KB Wrong output format.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB n=5
2 Incorrect 2 ms 5068 KB Wrong output format.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB n=5
2 Incorrect 2 ms 5068 KB Wrong output format.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB n=5
2 Incorrect 2 ms 5068 KB Wrong output format.
3 Halted 0 ms 0 KB -