Submission #789255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789255	2023-07-21T08:40:57 Z	박상훈(#10042)	Tourism (JOI23_tourism)	C++17	7 / 100	102 ms	25396 KB

tourism

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int B = 400, INF = 1e9 + 100;

int n;
vector<int> adj[100100];
int a[100100], ans[100100], cnt[100100], val;
multiset<pair<int, int>> st;

int in[100100], out[100100], dep[100100], INV[100100], cnti;
int dfn[100100], cntd;

struct Query{
	int s, e, i;
	Query(){}
	Query(int _s, int _e, int _i): s(_s), e(_e), i(_i) {}

	bool operator < (const Query &Q) const{
		if (s / B == Q.s / B){
			if ((s / B) % 2 == 0) return e < Q.e;
			return e > Q.e;
		} 
		return s / B < Q.s / B;
	}
}Q[100100];

struct Seg{
	pair<int, int> tree[400400];
	int sz;

	void init(int n){
		sz = n;
		// for (int i=sz;i<sz*2;i++) printf("(%d, %d) ", tree[i].first, tree[i].second);
		// printf("\n");
		for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
	}

	int query(int l, int r){
		// printf("  query %d to %d\n", l, r);
		++r;
		pair<int, int> ret = {INF, 0};
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret = min(ret, tree[l++]);
			if (r&1) ret = min(ret, tree[--r]);
		}

		return ret.second;
	}
}rmq;

struct Seg2{
	int tree[400400];
	int sz;

	void init(int n){
		sz = n;
		fill(tree, tree+sz*2, -INF);
	}

	void update(int p, int x){
		p += sz;
		tree[p] = x;
		for(p>>=1;p;p>>=1) tree[p] = max(tree[p<<1], tree[p<<1|1]);
	}

	int query(int l, int r){
		// printf("  query %d to %d\n", l, r);
		++r;
		int ret = -INF;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret = max(ret, tree[l++]);
			if (r&1) ret = max(ret, tree[--r]);
		}

		return ret;
	}
}prf;

struct Seg3{
	int tree[400400];
	int sz;

	void init(int n){
		sz = n;
		fill(tree, tree+sz*2, INF);
	}

	void update(int p, int x){
		p += sz;
		tree[p] = x;
		for(p>>=1;p;p>>=1) tree[p] = min(tree[p<<1], tree[p<<1|1]);
	}

	int query(int l, int r){
		// printf("  query %d to %d\n", l, r);
		++r;
		int ret = INF;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret = min(ret, tree[l++]);
			if (r&1) ret = min(ret, tree[--r]);
		}

		return ret;
	}
}suf;


void dfs(int s, int pa = 0){
	in[s] = ++cnti;
	dep[s] = dep[pa] + 1;
	rmq.tree[cnti + rmq.sz] = {dep[s], s};

	dfn[s] = ++cntd;
	INV[cntd] = s;
	
	for (auto &v:adj[s]) if (v!=pa){
		dfs(v, s);

		++cnti;
		rmq.tree[cnti + rmq.sz] = {dep[s], s};
	}

	// out[s] = ++cnti;
	// rmq.tree[cnti + rmq.sz] = {dep[s], s};
}

int dist(int x, int y){
	int lca = rmq.query(min(in[x], in[y]), max(in[x], in[y]));
	// printf(" calc %d %d -> %d (lca = %d)\n", x, y, dep[x] + dep[y] - dep[lca] * 2, lca);
	return dep[x] + dep[y] - dep[lca] * 2;
}

int s0, e0;
void push(int x){
	x = a[x];
	// printf("push %d\n", x);
	cnt[x]++;
	if (cnt[x]==1){
		if (s0==-1){
			s0 = e0 = x;
			val = 0;
		}

		else{
			int prv = prf.query(1, dfn[x]-1);
			int nxt = suf.query(dfn[x]+1, n);

			// printf(" ok %d %d\n", prv, nxt);

			if (prv==-INF) prv = e0;
			else prv = INV[prv];
			if (nxt==INF) nxt = s0;
			else nxt = INV[nxt];

			val -= dist(prv, nxt);
			val += dist(prv, x);
			val += dist(x, nxt);

			if (dfn[e0] < dfn[x]) e0 = x;
			if (dfn[x] < dfn[s0]) s0 = x;

			// printf("prv = %d / nxt = %d / range: [%d, %d] / val = %d\n", prv, nxt, s0, e0, val);
		}

		prf.update(dfn[x], dfn[x]);
		suf.update(dfn[x], dfn[x]);

		



		// auto iter = st.emplace(in[x], x);

		// auto prv = (iter==st.begin())?(prev(st.end())):(prev(iter));
		// auto nxt = (next(iter)==st.end())?(st.begin()):(next(iter));

		// val -= dist(prv->second, nxt->second);
		// val += dist(prv->second, iter->second);
		// val += dist(iter->second, nxt->second);
	}

	// printf(" ok val = %d\n", val);
}

void pop(int x){
	x = a[x];
	// printf("pop %d\n", x);
	cnt[x]--;
	if (cnt[x]==0){
		if (s0==e0){
			s0 = e0 = -1;
			val = 0;
		}

		else{
			int prv = prf.query(1, dfn[x]-1);
			int nxt = suf.query(dfn[x]+1, n);

			if (prv==-INF) prv = e0;
			else prv = INV[prv];
			if (nxt==INF) nxt = s0;
			else nxt = INV[nxt];

			val += dist(prv, nxt);
			val -= dist(prv, x);
			val -= dist(x, nxt);

			if (e0==x) e0 = prv;
			if (s0==x) s0 = nxt;

			// printf("prv = %d / nxt = %d / range: [%d, %d] / val = %d\n", prv, nxt, s0, e0, val);
		}

		prf.update(dfn[x], -INF);
		suf.update(dfn[x], INF);


		// auto iter = st.find(pair<int, int>(in[x], x));
		// assert(iter!=st.end());

		// auto prv = (iter==st.begin())?(prev(st.end())):(prev(iter));
		// auto nxt = (next(iter)==st.end())?(st.begin()):(next(iter));

		// val += dist(prv->second, nxt->second);
		// val -= dist(prv->second, iter->second);
		// val -= dist(iter->second, nxt->second);

		// st.erase(iter);
	}

	// printf(" ok val = %d\n", val);
}

int main(){
	int m, q;
	scanf("%d %d %d", &n, &m, &q);

	for (int i=1;i<=n-1;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	for (int i=1;i<=m;i++) scanf("%d", a+i);

	for (int i=1;i<=q;i++){
		scanf("%d %d", &Q[i].s, &Q[i].e);
		Q[i].i = i;
	}

	rmq.sz = n*2+10;
	dfs(1);
	rmq.init(n*2+10);

	sort(Q+1, Q+q+1);
	int l = 1, r = 0;

	s0 = e0 = -1;
	prf.init(m+1);
	suf.init(m+1);

	for (int i=1;i<=m;i++){
		prf.update(i, a[i]);
		suf.update(i, a[i]);
	}

	for (int i=1;i<=q;i++){
		ans[Q[i].i] = prf.query(Q[i].s, Q[i].e) - suf.query(Q[i].s, Q[i].e) + 1;
	}

	for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
	return 0;

	for (int i=1;i<=q;i++){
		while(r<Q[i].e){
			++r;
			push(r);
		}

		while(l>Q[i].s){
			--l;
			push(l);
		}

		while(r>Q[i].e){
			pop(r);
			r--;
		}

		while(l<Q[i].s){
			pop(l);
			l++;
		}

		ans[Q[i].i] = val/2 + 1;
	}

	for (int i=1;i<=q;i++) printf("%d\n", ans[i]);

}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:238:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:242:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:247:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 |  for (int i=1;i<=m;i++) scanf("%d", a+i);
      |                         ~~~~~^~~~~~~~~~~
tourism.cpp:250:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  250 |   scanf("%d %d", &Q[i].s, &Q[i].e);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	5844 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	5844 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	2 ms	5844 KB	Output is correct
2	Correct	3 ms	5844 KB	Output is correct
3	Correct	3 ms	5816 KB	Output is correct
4	Correct	69 ms	17980 KB	Output is correct
5	Correct	68 ms	20432 KB	Output is correct
6	Correct	66 ms	22148 KB	Output is correct
7	Correct	102 ms	25320 KB	Output is correct
8	Correct	95 ms	25216 KB	Output is correct
9	Correct	96 ms	25300 KB	Output is correct
10	Correct	100 ms	25396 KB	Output is correct
11	Correct	94 ms	25212 KB	Output is correct
12	Correct	89 ms	25036 KB	Output is correct
13	Correct	83 ms	24988 KB	Output is correct
14	Correct	82 ms	25084 KB	Output is correct
15	Correct	50 ms	21580 KB	Output is correct
16	Correct	76 ms	24828 KB	Output is correct
17	Correct	65 ms	10808 KB	Output is correct