QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178598#6332. Two CurrenciesRNG_Sword_S110 590ms574488kbC++143.2kb2023-09-14 08:51:092023-09-14 08:51:10

Judging History

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

  • [2023-09-14 08:51:10]
  • 评测
  • 测评结果:0
  • 用时:590ms
  • 内存:574488kb
  • [2023-09-14 08:51:09]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed rt[800010];
pair<int,int> operator+(pair<int,int> x,pair<int,int> y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}
namespace ds1
{
	int t[50000010];
	signed cnt[50000010],ls[50000010],rs[50000010],tot=0;
	void update(signed &x,int l,int r,int p,int v)
	{
		if(!x)
			x=++tot;
		t[x]+=v;cnt[x]++;
		if(l==r)
			return ;
		int mid=(l+r)/2;
		if(p<=mid)
			update(ls[x],l,mid,p,v);
		else
			update(rs[x],mid+1,r,p,v);
	}
	vector<int> cur;
	int query(int l,int r,int k)
	{
		if(l==r)
			return (k/l);
		int lcnt=0,lsum=0,mid=(l+r)/2;
		for(int x:cur)
			lcnt+=cnt[ls[x]],lsum+=t[ls[x]];//cout<<x<<' ';
//		cout<<endl;
		if(lsum<=k)
		{
			for(int &x:cur)
				x=rs[x];
			return query(mid+1,r,k-lsum)+lcnt;
		}
		for(int &x:cur)
			x=ls[x];
		return query(l,mid,k);
	}
};
vector<int> v;
namespace ds2
{
	void insert(int x,int l,int r,int p,int v)
	{
		ds1::update(rt[x],1,1e9,v,v);	
		if(l==r)
			return ;
		int mid=(l+r)/2;
		if(p<=mid)
			insert(x<<1,l,mid,p,v);
		else
			insert(x<<1|1,mid+1,r,p,v);
	}	
	void findit(int x,int l,int r,int ll,int rr)
	{
		if(r<ll||rr<l)
			return ;
		if(ll<=l&&r<=rr)
		{
			v.push_back(rt[x]);
			return ;
		}
		int mid=(l+r)/2;
		findit(x<<1,l,mid,ll,rr);
		findit(x<<1|1,mid+1,r,ll,rr);
	}
};
vector<int> e[200010],id[200010];
int n,m,q;
vector<int> cc[200010];
vector<int> val[200010];
namespace ds3
{
	int fa[200010],sz[200010],dfn[200010],cnt=0;
	int top[200010],mxson[200010],dp[200010];
	int sum[200010];
	void dfs1(int x,int pre)
	{
		fa[x]=pre;sz[x]=1;dp[x]=dp[pre]+1;
		sum[x]=sum[pre]+val[x].size();
		for(int y:e[x])
			if(y!=pre)
			{
				dfs1(y,x),sz[x]+=sz[y];
				if(sz[y]>sz[mxson[x]])
					mxson[x]=y; 
			}
	}
	void dfs2(int x,int pre)
	{
		dfn[x]=++cnt;top[x]=pre;
		for(int y:val[x])
			ds2::insert(1,1,n,dfn[x],y);
		if(mxson[x])
			dfs2(mxson[x],pre);
		for(int y:e[x])
			if(y!=fa[x]&&y!=mxson[x])
				dfs2(y,y);
	}
	int query(int x,int y,int v)
	{
		::v.clear();
		int ans=sum[x]+sum[y];
	//	cout<<ans<<endl;
		while(top[x]!=top[y])
		{
			if(dp[x]<dp[y])
				swap(x,y);
	//		cout<<dfn[top[x]]<<' '<<dfn[x]<<endl;
			ds2::findit(1,1,n,dfn[top[x]],dfn[x]);
			x=fa[top[x]];
		}
		if(dp[x]>dp[y])
			swap(x,y);
	//	cout<<dfn[x]+1<<' '<<dfn[y]<<endl;
		if(x!=y)
			ds2::findit(1,1,n,dfn[x]+1,dfn[y]);
		ans-=2*sum[x];
		ds1::cur=::v; 
	//	cout<<ans<<endl;
		return ans-ds1::query(1,1e9,v);
	}
	void build()
	{
		dfs1(1,0);
		dfs2(1,1);
	}
};
void dfs(int x,int pre)
{
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==pre)
			continue;
		for(int z:cc[id[x][i]])
			val[y].push_back(z);
		dfs(y,x);
	}
}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		e[x].push_back(y);id[x].push_back(i);
		e[y].push_back(x);id[y].push_back(i);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		cc[x].push_back(y);
	}
	dfs(1,0);ds3::build();
	while(q--)
	{
		int x,y,a,b;
		scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		int res=ds3::query(x,y,b);
		if(res<=a)
			printf("%lld\n",a-res);
		else
			puts("-1");
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 13ms
memory: 44952kb

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:

489564527
1036709094
1063710485
392742980
1591534029
615471693
956126643
22
21
643661787
-1
983129477
33
1102117706
0
7
4
-1
621458139
2
9
17
5
4
-1
8
-1
529950077
1129077160
-1
24
1637400385
4
493354078
785690446
0
-1
-1
6
-1
12
8
-1
22
-1
13
11
26
7
-1
2
0
1214718881
2
6
130078594
-1
965037695
981...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 424ms
memory: 138784kb

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:

36
-1
6
53
-1
-1
1069231327
-1
766963193
-1
-1
-1
29
-1
-1
-1
-1
444125143
18
292129848
1068454216
1719753505
8
1035486729
1327996658
1406240978
16
1596215544
31
24
1504247617
5
19
2
-1
4
-1
381362907
22
-1
1089696991
1434790472
8
10
-1
0
-1
19
-1
14
8
960058129
1570009375
-1
24
728928959
-1
19
9592...

result:

wrong answer 3rd numbers differ - expected: '12', found: '6'

Subtask #3:

score: 0
Wrong Answer

Test #59:

score: 0
Wrong Answer
time: 590ms
memory: 574488kb

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:

-1
1044808866
-1
1560551243
1680858466
2440
1211526409
-1
29509
1002460821
1086724608
890
-1
1080812111
1212591145
1275921602
2347
5427
4829
44377
283904974
60823
508
837102571
947262911
-1
1712492316
3856
9692
6576
798657137
1656135303
1473
14691
26175
-1
27082
-1
9735
3846
1303837223
-1
621963028
...

result:

wrong answer 2nd numbers differ - expected: '701714740', found: '1044808866'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%