| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 892709 |
2023-12-25T17:44:44 Z |
LucaIlie |
Tourism (JOI23_tourism) |
C++17 |
|
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++ )
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
