제출 #892731

#제출 시각아이디문제언어결과실행 시간메모리
892731LucaIlieTourism (JOI23_tourism)C++17
10 / 100
5084 ms95044 KiB
#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; dfs( v, u ); maxLQ[u] = max( maxLQ[u], maxLQ[v] ); minHQ[u] = min( minHQ[u], minHQ[v] ); } 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; 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() ); Tree virtualSpotsTree; 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; }

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

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:146:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for ( int i = 2; i < virtualSpots.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
tourism.cpp:155:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for ( int i = 1; i < virtualSpots.size(); i++ )
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...