QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111444#6332. Two CurrenciesFlamire0 214ms71912kbC++142.2kb2023-06-07 08:53:582023-06-07 08:54:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-07 08:54:02]
  • 评测
  • 测评结果:0
  • 用时:214ms
  • 内存:71912kb
  • [2023-06-07 08:53:58]
  • 提交

answer

#include <bits/stdc++.h>
#define N 100011
#define ll long long
using namespace std;
int n,m,q,fa[N][21],ndE[N],dep[N],rt[N],sz,U[N],V[N];vector<int> w[N];
vector<int> G[N];
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);for(int i=20;~i;--i)if(dep[u]-(1<<i)>=dep[v])u=fa[u][i];if(u==v)return u;
	for(int i=20;~i;--i)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];
}
ll sum[N*50],dis[N];int lc[N*50],rc[N*50],cnt[N*50];
void pushup(int x){sum[x]=sum[lc[x]]+sum[rc[x]];cnt[x]=cnt[lc[x]]+cnt[rc[x]];}
void add(int k,ll v,int L,int R,int x,int &c)
{
	if(!c)c=++sz;if(L==R){sum[c]=sum[x]+v;cnt[c]=cnt[x]+1;return;}
	if(k<=L+R>>1)rc[c]=rc[x],add(k,v,L,L+R>>1,lc[x],lc[c]);else lc[c]=lc[x],add(k,v,(L+R>>1)+1,R,rc[x],rc[c]);pushup(c);
}
int bin(int r1,int r2,int r3,int r4,ll v,int L,int R)
{
	if(L==R)return L;
	if(sum[rc[r1]]+sum[rc[r2]]-sum[rc[r3]]-sum[rc[r4]]>v)return bin(rc[r1],rc[r2],rc[r3],rc[r4],v,(L+R>>1)+1,R);
	else return bin(lc[r1],lc[r2],lc[r3],lc[r4],v-(sum[rc[r1]]+sum[rc[r2]]-sum[rc[r3]]-sum[rc[r4]]),L,L+R>>1);
}
int query(int l,int r,int L,int R,int x)
{
	if(!x)return 0;if(l<=L&&R<=r)return cnt[x];int ans=0;
	if(l<=L+R>>1)ans+=query(l,r,L,L+R>>1,lc[x]);if(r>L+R>>1)ans+=query(l,r,(L+R>>1)+1,R,rc[x]);return ans;
}
void dfs(int u,int f)
{
	fa[u][0]=f;for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];dep[u]=dep[f]+1;
	for(int v:G[u])if(v^f)dfs(v,u);
}
void dfs_(int u,int f)
{
	int lst=rt[f];
	for(int x:w[u])add(x,x,1,1e9,lst,rt[u]),lst=rt[u];dis[u]=dis[f];for(int x:w[u])dis[u]+=x;
	for(int v:G[u])if(v^f)dfs_(v,u);
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);U[i]=u;V[i]=v;}
	dfs(1,0);
	for(int i=1;i<n;++i)if(dep[U[i]]<dep[V[i]])ndE[i]=V[i];else ndE[i]=U[i];
	for(int i=1;i<=m;++i){int p,c;scanf("%d%d",&p,&c);w[ndE[p]].push_back(c);}
	dfs_(1,0);
	while(q--)
	{
		int s,t,x;ll y;scanf("%d%d%d%lld",&s,&t,&x,&y);
		int l=lca(s,t);ll Dis=dis[s]+dis[t]-dis[l]-dis[l];
		int id=bin(rt[s],rt[t],rt[l],rt[l],Dis-y-1,1,1e9);
		int num=query(id,1e9,1,1e9,rt[s])+query(id,1e9,1,1e9,rt[t])-2*query(id,1e9,1,1e9,rt[l]);
		if(num>x)printf("-1\n");else printf("%d\n",x-num);
	}return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

1831 1865 1153
832 1698
1672 1619
634 920
328 1244
571 1279
1673 1815
1098 92
1320 432
244 636
991 1446
308 569
1118 1356
1733 71
497 1679
1699 635
1254 1295
853 345
364 1396
1183 1134
524 1557
1642 1262
1767 459
918 794
1644 539
902 1046
334 1789
1691 1548
1298 520
1763 216
1161 1065
682 1167
1282 ...

output:

378730605
649537044
339843141
362013697
600127619
123276007
749019778
32
13
54569538
9
26669081
33
255375699
4
8
6
4
427653834
15
-1
26
11
9
-1
15
18
265022184
218253041
-1
24
849614439
11
29092527
539604026
13
18
-1
21
5
12
11
-1
21
-1
16
14
41
19
4
2
3
546008661
9
15
86261072
-1
448122840
87357746...

result:

wrong answer 8th numbers differ - expected: '22', found: '32'

Subtask #2:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 214ms
memory: 61404kb

input:

99819 89735 60985
59741 24953
61387 12293
53761 1828
60970 60534
40598 48807
21876 21232
29527 13335
84269 40756
89571 12996
25757 40587
52477 63347
41372 69243
16391 58678
40854 39513
84384 91744
62938 60371
81932 45504
34121 54746
51945 14294
883 85344
78845 51797
45025 76590
37694 65493
4118 2588...

output:

53
-1
24
44
14
13
652673843
19
422622756
3
9
-1
29
-1
3
16
23
427634455
34
265926271
263974211
877045993
15
288833077
997549690
644774220
10
995218986
27
30
924036742
33
18
13
4
9
-1
4393606
19
11
932888431
991013529
21
15
4
9
17
28
9
31
9
502124020
726366843
10
20
119719836
6
37
217737158
1
9415918...

result:

wrong answer 1st numbers differ - expected: '36', found: '53'

Subtask #3:

score: 0
Wrong Answer

Test #59:

score: 0
Wrong Answer
time: 187ms
memory: 71912kb

input:

95629 64841 64314
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:

8134
701714740
22117
610354140
816755067
9110
245932872
4006
40385
866966613
744072492
1428
26112
969398264
588051152
381506396
4720
7219
10856
53274
195466300
68362
956
459304253
400544113
13586
787773518
4202
13225
9102
322820913
900985028
14008
29635
27054
16697
40829
25336
14887
8214
537036842
3...

result:

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

Subtask #4:

score: 0
Skipped

Dependency #1:

0%