Submission #889169

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889169	2023-12-19T05:06:34 Z	thunopro	Tourism (JOI23_tourism)	C++14	7 / 100	62 ms	44372 KB

tourism

#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009 
#define ll long long
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef vector<ll> vl ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 
typedef pair<ll,ll> pll ;  

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;} 
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int n , m , nq ; 
vi adjList [maxn] ;
 
int seeing [maxn] ; 
pii query [maxn] ; 

int par [maxn][20] , dep [maxn] , tin [maxn] , timeDfs ; 
void dfs ( int u = 1 )
{
	tin [u] = ++ timeDfs ; 
	for ( auto v : adjList [u] ) 
	{
		if ( v == par [u][0] ) continue ; 
		par [v][0] = u , dep [v] = dep [u] + 1 ; 
		for ( int i = 1 ; i <= LOG ; i ++ ) par [v][i] = par[par[v][i-1]][i-1] ; 
		dfs (v) ; 
	}
}

int lca ( int u , int v ) 
{
	if ( dep [u] < dep [v] ) swap (u,v) ; 
	int h = dep [u] - dep [v] ; 
	for ( int i = LOG ; i >= 0 ; i -- ) if ( h >> i & 1 ) u = par [u][i] ;
	if ( u == v ) return u ; 
	for ( int i = LOG ; i >= 0 ; i -- ) if ( par [u][i] != par [v][i] ) u = par [u][i] , v = par [v][i] ; 
	return par [u][0] ; 
} 

int dis ( int u , int v ) 
{
	return dep [u] + dep [v] - 2*dep[lca(u,v)] ; 
}

bool cmp ( int u , int v ) 
{
	return tin [u] < tin [v] ; 
}
void sub1 () 
{
	for ( int run = 1 ; run <= nq ; run ++ )
	{
		int l = query [run].fi , r = query [run].se ; 
		vi v ; 
		for ( int i = l ; i <= r ; i ++ ) v . pb (seeing[i]) ;
		sort (v.begin(),v.end(),cmp) ; 
		int last = 0 ; 
		int res = 0 ; 
		for ( auto x : v ) 
		{
			if ( last ) res += dis (last,x) ;
			last = x ; 
		}
		res += dis (last,v[0]) ; 
		cout << res / 2 + 1 << "\n" ; 
	}
}	


bool check_isline () 
{
	for ( int i = 1 ; i <= n ; i ++ ) if ( (int)adjList[i].size () > 2 ) return false ; 
	if ( adjList [1] . size () != 1 || adjList [n].size () != 1 ) return false ; 
	return true ; 
}

int L [maxn][20][2] ; 
int get_max ( int l , int r ) 
{
	int x = __lg(r-l+1) ; 
	return max (L[l][x][1],L[r-(1<<x)+1][x][1]) ; 
}
int get_min ( int l , int r ) 
{
	int x = __lg(r-l+1) ; 
	return min (L[l][x][0],L[r-(1<<x)+1][x][0]) ; 
}

void sub2 () 
{
	for ( int i = 1 ; i <= m ; i ++ ) L [i][0][0] = L [i][0][1] = seeing [i] ; 
	for ( int j = 1 ; j <= __lg (m) ; j ++ ) 
	{
		for ( int i = 1 ; i <= m-(1<<j)+1 ; i ++ ) 
		{
			L [i][j][0] = min ( L[i][j-1][0],L[i+(1<<(j-1))][j-1][0]) ; 
			L [i][j][1] = max ( L[i][j-1][1],L[i+(1<<(j-1))][j-1][1]) ; 
		}
	}
	for ( int run = 1 ; run <= nq ; run ++ ) 
	{
		int l = query [run].fi , r = query [run].se ; 
		cout << get_max (l,r) - get_min (l,r) + 1 << "\n" ; 
	}
}
int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; cout.tie(0) ; 
//	rf () ; 
	cin >> n >> m >> nq ; 
	
	for ( int i = 1 ; i < n ; i ++ ) 
	{
		int u , v ; cin >> u >> v ; 
		adjList [u] . pb (v) ; 
		adjList [v] . pb (u) ; 
	}
	
	for ( int i = 1 ; i <= m ; i ++ ) cin >> seeing [i] ; 
	
	for ( int i = 1 ; i <= nq ; i ++ ) cin >> query [i].fi >> query [i].se ; 
	dfs () ; 
	
	sub2 () ; re 
	if ( check_isline () ) sub2 () ; 
	else sub1 () ; 
}

Compilation message

tourism.cpp: In function 'void rf()':
tourism.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	8536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	8536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8536 KB	Output is correct
2	Correct	2 ms	8668 KB	Output is correct
3	Correct	2 ms	10844 KB	Output is correct
4	Correct	40 ms	35376 KB	Output is correct
5	Correct	47 ms	35924 KB	Output is correct
6	Correct	47 ms	41040 KB	Output is correct
7	Correct	59 ms	44112 KB	Output is correct
8	Correct	60 ms	44368 KB	Output is correct
9	Correct	62 ms	44308 KB	Output is correct
10	Correct	59 ms	44372 KB	Output is correct
11	Correct	59 ms	44116 KB	Output is correct
12	Correct	57 ms	44292 KB	Output is correct
13	Correct	60 ms	44372 KB	Output is correct
14	Correct	56 ms	44156 KB	Output is correct
15	Correct	42 ms	27152 KB	Output is correct
16	Correct	58 ms	43856 KB	Output is correct
17	Correct	31 ms	25424 KB	Output is correct