QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461619#6340. TourismRafi22#0 43ms15184kbC++203.8kb2024-07-02 20:48:262024-07-02 20:48:27

Judging History

你现在查看的是最新测评结果

  • [2024-07-02 20:48:27]
  • 评测
  • 测评结果:0
  • 用时:43ms
  • 内存:15184kb
  • [2024-07-02 20:48:26]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif


#define ll long long
#define pb push_back
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
#define endl '\n'
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=998244353;

const int N=100007,S=300,pot=1<<17,LG=17;


int seg[2*pot+7];
int seg1[2*pot+7];

int que(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg[v];
	if(r<a||l>b) return inf;
	return min(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
int que1(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg1[v];
	if(r<a||l>b) return -inf;
	return max(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
}

vector<pair<int,int>>W[N];


int BIT[N];

void ins(int v)
{
	for(;v<N;v+=v&-v) BIT[v]++;
}
int QUE(int v)
{
	int res=0;
	for(;v>0;v-=v&-v) res+=BIT[v];
	return res;
}

struct Z
{
	int l,r,i;
};

bool cmp(Z a,Z b)
{
	if(a.l/S==b.l/S) return a.r<b.r;
	else return a.l<b.l;
}

vector<int>G[N];
int ile[N];
int c[N];
int res[N];
int pre[N],post[N],cc;
int ord[N];
int d[N];
int xd[N];
int skok[N][LG];

void dfs(int v,int o)
{
	
	pre[v]=++cc;
	ord[cc]=v;
	skok[v][0]=o;
	FOR(i,1,LG-1) skok[v][i]=skok[skok[v][i-1]][i-1];
	for(auto u:G[v])
	{
		if(u==o) continue;
		d[u]=d[v]+1;
		dfs(u,v);
	}
	post[v]=cc;
	xd[pre[v]]=post[v];
}

bool anc(int u,int v)
{
	return pre[u]<=pre[v]&&post[u]>=post[v];
}
int lca(int u,int v)
{
	if(anc(u,v)) return u;
	ROF(i,LG-1,0) if(!anc(skok[u][i],v)) u=skok[u][i];
	debug("lca",u,v,skok[u][0]);
	return skok[u][0];
}


int ans;

set<int>SS;

void add(int v)
{
	debug("add",v);
	if(sz(SS)>2)
	{
		int D=-inf;
		set<int>::iterator it=SS.lower_bound(pre[v]);
		if(*it!=inf)
		{
			int l=lca(v,ord[*it]);
			D=max(D,d[l]);
		}
		it--;
		if(*it!=-inf)
		{
			int l=lca(v,ord[*it]);
			D=max(D,d[l]);
		}
		debug(d[v]-D);
		ans+=d[v]-D;
	}
	else ans+=d[v]+1;
	SS.insert(pre[v]);
}



void del(int v)
{
	debug("del",v);
	SS.erase(pre[v]);
	if(sz(SS)>2)
	{
		int D=-inf;
		set<int>::iterator it=SS.lower_bound(pre[v]);
		if(*it!=inf)
		{
			int l=lca(v,ord[*it]);
			D=max(D,d[l]);
		}
		it--;
		if(*it!=-inf)
		{
			int l=lca(v,ord[*it]);
			D=max(D,d[l]);
		}
		ans-=d[v]-D;
	}
	else ans-=d[v]+1;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	FOR(i,1,n-1)
	{
		int a,b;
		cin>>a>>b;
		G[a].pb(b);
		G[b].pb(a);
	}
	dfs(1,1);
	FOR(i,1,2*pot)
	{
		seg[i]=inf;
		seg1[i]=-inf;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>c[i];
		seg[i+pot-1]=pre[c[i]];
		seg1[i+pot-1]=pre[c[i]];
	}
	for(int i=pot-1;i>0;i--)
	{
		seg[i]=min(seg[2*i],seg[2*i+1]);
		seg1[i]=max(seg1[2*i],seg1[2*i+1]);
	}
	vector<Z>Q;
	FOR(i,1,q)
	{
		int l,r;
		cin>>l>>r;
		Q.pb({l,r,i});
		int L=que(1,l,r,1,pot),R=que1(1,l,r,1,pot);
		W[L].pb({R,i});
	}
	sort(all(Q),cmp);
	int L=1,R=0;
	SS.insert(inf);
	SS.insert(-inf);
	for(auto x:Q)
	{
		debug("Q",x.l,x.r);
		while(L<x.l)
		{
			del(c[L]);
			L++;
		}
		while(L>x.l)
		{
			L--;
			add(c[L]);
		}
		while(R>x.r)
		{
			del(c[R]);
			R--;
		}
		while(R<x.r)
		{
			R++;
			add(c[R]);
		}
		res[x.i]=ans;
	}
	FOR(i,1,n)
	{
		if(i>1) ins(xd[i]);
		for(auto [j,k]:W[i]) res[k]-=QUE(n)-QUE(j-1);
	}
	FOR(i,1,q) cout<<res[i]<<endl;
	
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 8312kb

input:

166 249 224
158 52
52 82
158 36
117 158
119 117
5 82
158 18
22 36
82 143
105 36
22 152
36 92
117 2
123 158
5 134
119 89
31 119
92 48
105 149
149 17
108 31
134 50
3 52
63 158
3 51
42 22
17 10
103 158
50 122
92 85
50 78
117 159
36 20
143 115
158 83
20 4
142 22
23 3
96 10
19 134
8 10
151 92
65 108
89 5...

output:

-48
-1852
-727
-40
-90
-2660
-3035
-130
-856
-1335
-87
-1491
-689
-37
25
-211
-29
-70
-3047
-148
-1489
-2863
-49
-165
-768
-3118
-892
-719
-787
-2355
-77
-1410
-42
-3084
-337
-1887
-857
-48
-98
-262
-1163
-51
-271
-899
-927
-855
-1502
-1099
-81
-3076
-219
-466
-49
-433
-738
-1434
-1960
-56
-1709
-35...

result:

wrong answer 1st numbers differ - expected: '67', found: '-48'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #56:

score: 0
Time Limit Exceeded

input:

55321 88650 75523
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:


result:


Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 43ms
memory: 15184kb

input:

54738 54525 1797
45211 4527
4527 43609
4527 19876
16325 43609
32183 4527
16325 32579
43609 25554
32183 38972
45211 53953
16325 19810
10881 19810
45211 12698
27967 19810
25554 46338
51894 45211
25388 16325
512 25554
43609 7820
10206 512
30021 32183
48647 43609
46338 44138
16766 7820
10023 53953
19810...

output:

276
238
198
214
294
240
233
266
184
241
207
241
256
225
215
222
190
269
221
242
287
225
215
252
273
203
281
186
259
195
152
183
206
241
218
205
241
233
194
239
258
244
267
339
224
205
242
202
260
275
173
243
178
228
251
242
239
231
203
249
277
215
202
169
243
258
208
306
232
231
211
224
249
256
203
...

result:

wrong answer 104th numbers differ - expected: '281', found: '270'

Subtask #5:

score: 0
Time Limit Exceeded

Test #102:

score: 0
Time Limit Exceeded

input:

55965 89652 95687
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%