oj.uz

답안 #892709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
892709 2023-12-25T17:44:44 Z LucaIlie Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 91252 KB 
#include <bits/stdc++.h>

using namespace std;

struct Tree {
    struct edge {
        int u, v, c;

        int other( int w ) {
            return u ^ v ^ w;
        }
    };

    int n;
    vector<edge> edges;
    vector<vector<int>> adj;
    vector<int> depth, timeIn, timeOut;
    vector<vector<int>> parent;
    vector<int> maxLQ, minHQ;

    void resize( int _size ) {
        n = _size;

        edges.clear();
        adj.clear();
        adj.resize( n + 1 );

        depth.clear();
        depth.resize( n + 1 );
        timeIn.clear();
        timeIn.resize( n + 1 );
        timeOut.clear();
        timeOut.resize( n + 1 );

        maxLQ.resize( n + 1 );
        for ( int i = 0; i <= n; i++ )
            maxLQ[i] = 0;
        minHQ.resize( n + 1 );
        for ( int i = 0; i <= n; i++ )
            minHQ[i] = INT_MAX;

        parent.clear();
        parent.resize( (int)log2( n ) + 1 );
        for ( int i = 0; i <= log2( n ); i++ )
            parent[i].resize( n + 1 );
    }

    void add_edge( int u, int v, int c ) {
        adj[u].push_back( edges.size() );
        adj[v].push_back( edges.size() );
        edges.push_back( { u, v, c } );
    }
    void addMaxLQ( int v, int val ) {
        maxLQ[v] = max( maxLQ[v], val );
    }

    void addMinHQ( int v, int val ) {
        minHQ[v] = min( minHQ[v], val );
    }

    int timee;
    void dfs( int u, int p ) {
        parent[0][u] = p;
        timeIn[u] = ++timee;
        for ( int e: adj[u] ) {
            int v = edges[e].other( u ), c = edges[e].c;
            if ( v == p )
                continue;
            depth[v] = depth[u] + c;
            maxLQ[u] = max( maxLQ[u], maxLQ[v] );
            minHQ[u] = min( minHQ[u], minHQ[v] );
            dfs( v, u );
        }
        timeOut[u] = timee;
    }

    void init( int root ) {
        timee = 0;
        dfs( root, 0 );
        for ( int l = 1; l <= log2( n ); l++ ) {
            for ( int v = 1; v <= n; v++ )
                parent[l][v] = parent[l - 1][parent[l - 1][v]];
        }
    }

    int lca( int u, int v ) {
        if ( depth[u] > depth[v] )
            swap( u, v );

        for ( int l = log2( n ); l >= 0; l-- ) {
            if ( depth[parent[l][v]] >= depth[u] )
                v = parent[l][v];
        }

        if ( u == v )
            return v;

        for ( int l = log2( n ); l >= 0; l-- ) {
             if ( parent[l][u] != parent[l][v] ) {
                 u = parent[l][u];
                 v = parent[l][v];
             }
        }

        return parent[0][v];
    }

    bool inSubtree( int u, int v ) {
        return (timeIn[u] <= timeIn[v]) && (timeOut[v] <= timeOut[u]);
    }

};

const int MAX_M = 1e5;
const int MAX_Q = 1e5;
int answer[3000][3000];
Tree islandTree, virtualSpotsTree;
int spots[MAX_M], leftQ[MAX_Q], rightQ[MAX_Q];
unordered_map<int, int> valToPos;

void solve( int l, int r ) {
    if ( l > r )
        return;

    int mid = (l + r) / 2;
    solve( l, mid - 1 );
    solve( mid + 1, r );

    vector<int> rangeSpots, virtualSpots;
    virtualSpots.push_back( 0 );
    for ( int i = l; i <= r; i++ ) {
        rangeSpots.push_back( spots[i] );
        virtualSpots.push_back( spots[i] );
    }
    sort( rangeSpots.begin(), rangeSpots.end(), []( int u, int v ) { return islandTree.timeIn[u] < islandTree.timeIn[v]; } );
    for ( int i = 0; i < rangeSpots.size() - 1; i++ )
        virtualSpots.push_back( islandTree.lca( rangeSpots[i], rangeSpots[i + 1] ) );
    sort( virtualSpots.begin(), virtualSpots.end(), []( int u, int v ) { return islandTree.timeIn[u] < islandTree.timeIn[v]; } );
    virtualSpots.resize( unique( virtualSpots.begin(), virtualSpots.end() ) - virtualSpots.begin() );
    virtualSpotsTree.resize( virtualSpots.size() - 1 );

    vector<int> stack;
    stack.push_back( 1 );
    for ( int i = 2; i < virtualSpots.size(); i++ ) {
        while ( !stack.empty() && !islandTree.inSubtree( virtualSpots[stack.back()], virtualSpots[i] ) ) {
            stack.pop_back();
        }
        virtualSpotsTree.add_edge( stack.back(), i, islandTree.depth[virtualSpots[i]] - islandTree.depth[virtualSpots[stack.back()]] );
        stack.push_back( i );
    }

    valToPos.clear();
    for ( int i = 1; i < virtualSpots.size(); i++ )
        valToPos[virtualSpots[i]] = i;
    for ( int i = l; i <= mid; i++ )
        virtualSpotsTree.addMaxLQ( valToPos[spots[i]], i );
    for ( int i = mid; i <= r; i++ )
        virtualSpotsTree.addMinHQ( valToPos[spots[i]], i );
    virtualSpotsTree.init( valToPos[spots[mid]] );

    for ( auto e: virtualSpotsTree.edges ) {
        if ( virtualSpotsTree.depth[e.u] > virtualSpotsTree.depth[e.v] )
            swap( e.u, e.v );

        /*for ( int i = virtualSpotsTree.maxLQ[e.v]; i >= l; i-- ) {
            for ( int j = mid; j <= r; j++ )
                answer[i][j] += e.c;
        }
        for ( int j = virtualSpotsTree.minHQ[e.v]; j <= r; j++ ) {
            for ( int i = mid; i > virtualSpotsTree.maxLQ[e.v]; i-- )
                answer[i][j] += e.c;
        }*/

        for ( int i = l; i <= mid; i++ ) {
            for ( int j = mid; j <= r; j++ ) {
                if ( i <= virtualSpotsTree.maxLQ[e.v] || j >= virtualSpotsTree.minHQ[e.v] )
                    answer[i][j] += e.c;
            }
        }
    }
}

int main() {
    int n, m, q;

    cin >> n >> m >> q;
    islandTree.resize( n );
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        islandTree.add_edge( u, v, 1 );
    }
    for ( int i = 1; i <= m; i++ )
        cin >> spots[i];
    for ( int i = 1; i <= q; i++ )
        cin >> leftQ[i] >> rightQ[i];

    islandTree.init( 1 );
    solve( 1, m );

    for ( int i = 1; i <= q; i++ )
        cout << answer[leftQ[i]][rightQ[i]] + 1 << "\n";

    return 0;
}

Compilation message

tourism.cpp: In function 'void solve(int, int)':
tourism.cpp:136:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for ( int i = 0; i < rangeSpots.size() - 1; i++ )
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:144:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for ( int i = 2; i < virtualSpots.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
tourism.cpp:153:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for ( int i = 1; i < virtualSpots.size(); i++ )
      |                      ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Incorrect 4 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Incorrect 4 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 3 ms 2524 KB Output is correct
4 Execution timed out 5024 ms 48620 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 2294 ms 91252 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 4 ms 2396 KB Output is correct
4 Execution timed out 5025 ms 47096 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Incorrect 4 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -