oj.uz

Submission #889717

# Submission time Handle Problem Language Result Execution time Memory
889717 2023-12-20T06:06:16 Z vjudge1 Tourism (JOI23_tourism) C++17
7 / 100
 5000 ms 15032 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<type1, null_type, less_equal<type1>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std;
using namespace __gnu_pbds;

const int mod = 1e9+7;
const double PI = acos(-1.0);
const double epsilon = 1e-6;
const int N = 1e5+5;
vector<int> g[N];
int ans = 0;
int c[N],t2[N*4],t[N*4],dis[N],up[20][N],tin[N],tout[N];
bool vis[N];
int par[N];
int pos[N];
int timer;

void build(int v, int l, int r){
	if(l == r){
		t[v] = c[l];
		t2[v] = c[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
	t[v] = min(t[v * 2], t[v * 2 + 1]);
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
 
int getmn(int v, int tl, int tr, int l, int r) {
    if (l > tr || tl > r) return 1e18;
    if (l <= tl && tr <= r)return t[v];
    int tm = (tl + tr) / 2;
    return min(getmn(v * 2, tl, tm, l, r),getmn(v * 2 + 1, tm + 1, tr, l, r));
}

int getmx(int v, int tl, int tr, int l, int r) {
    if (l > tr || tl > r) return 0;
    if (l <= tl && tr <= r)return t2[v];
    int tm = (tl + tr) / 2;
    return max(getmx(v * 2, tl, tm, l, r),getmx(v * 2 + 1, tm + 1, tr, l, r));
}

void dfs(int v,int p,int l,int r){
	par[v] = p;
	if(l <= pos[v] && pos[v] <= r){
		int h = v;
		while(h != 0 && !vis[h]){
			vis[h] = 1;
			h = par[h];
		}
	}
	for(int to : g[v]){
		if(to != p) dfs(to,v,l,r);
	}
}

void solve(){
	int n,m,q;
	cin >> n >> m >> q;
	bool ok = 1;
	for(int i = 1; i < n; i++){
		int u,v; cin >> u >> v;
		g[u].pb(v); g[v].pb(u);
		if(!(u == i && v == i+1)) ok = 0;
	}
	for(int i = 1; i <= m; i++){
		cin >> c[i];
	}
	if(ok){
		build(1,1,m);
		while(q--){
			int l,r; cin >> l >> r;
			cout << getmx(1,1,m,l,r) - getmn(1,1,m,l,r) + 1 << '\n';
		}
		return;
	}
	for(int i = 1; i <= m; i++) pos[c[i]] = i;
	while(q--){
		int l,r; cin >> l >> r;
		dfs(c[l],0,l,r);
		int cnt = 0;
		for(int i = 1; i <= n; i++) cnt += vis[i],vis[i] = 0;
		cout << cnt << '\n';
	}
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

tourism.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 82 ms 13240 KB Output is correct
5 Correct 68 ms 11604 KB Output is correct
6 Correct 66 ms 13904 KB Output is correct
7 Correct 103 ms 14416 KB Output is correct
8 Correct 110 ms 15032 KB Output is correct
9 Correct 103 ms 14420 KB Output is correct
10 Correct 103 ms 14420 KB Output is correct
11 Correct 103 ms 14416 KB Output is correct
12 Correct 96 ms 14676 KB Output is correct
13 Correct 90 ms 14424 KB Output is correct
14 Correct 104 ms 14416 KB Output is correct
15 Correct 33 ms 12120 KB Output is correct
16 Correct 78 ms 14184 KB Output is correct
17 Correct 82 ms 11028 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Incorrect 2304 ms 9000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Execution timed out 5092 ms 9156 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -