QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#154186#7118. Closing Timepaul20088 119ms79336kbC++144.5kb2023-08-31 14:37:252023-08-31 14:37:26

Judging History

你现在查看的是测评时间为 2023-08-31 14:37:26 的历史记录

  • [2024-04-28 06:32:24]
  • 管理员手动重测本题所有提交记录
  • 测评结果:8
  • 用时:116ms
  • 内存:79440kb
  • [2023-08-31 14:37:26]
  • 评测
  • 测评结果:8
  • 用时:119ms
  • 内存:79336kb
  • [2023-08-31 14:37:25]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const long long N=4e5+5;

vector <long long> g[N],w[N];
long long fat[N],fa[N],son[N],a[N],n;
long long distx[N],disty[N];
bool inpath[N];

void dfsx(long long x,long long fa)
{
	for(long long i=0;i<g[x].size();i++)
	{
		long long to=g[x][i];
		if(to==fa)
			continue;

		fat[to]=x;
		distx[to]=distx[x]+w[x][i];
		dfsx(to,x);
	}
}

void dfsy(long long x,long long fa)
{
	for(long long i=0;i<g[x].size();i++)
	{
		long long to=g[x][i];
		if(to==fa)
			continue;

		disty[to]=disty[x]+w[x][i];
		dfsy(to,x);
	}
}

long long calc(long long k)
{
	priority_queue <long long,vector <long long>,greater<long long> > q;
	for(long long i=1;i<=n;i++)
		q.push(distx[i]);

	for(long long i=1;i<=n;i++)
		q.push(disty[i]);

	long long ans=0;
	while(!q.empty())
	{
		long long x=q.top();
		q.pop();
		k -= x, ans++;
		if(k<0)
			return ans-1;
	}
	return ans;
}

void add(long long x,long long y,long long z)
{
	g[x].push_back(y);
	w[x].push_back(z);
}

struct node
{
	long long sz,sum;
	long long id;

	bool operator <(const node& oth) const
	{
		return sum*oth.sz>oth.sum*sz;
	}
}val[N];

bool del[N],in[N];
pair <long long,long long> edge[N];
long long sumfirst[N];
long long cnt;
priority_queue <pair<long long,long long>,vector <pair<long long,long long> >,greater<pair<long long,long long> > > q;

long long gettop()
{
	while(del[q.top().second])
		q.pop();

	in[q.top().second]=true;
	long long ans=q.top().first;
	q.pop();
	return ans;
}

bool check(long long m,long long k) //判断是否可以取m个,上界为k
{
	if(m==cnt*2+1)
		return false;

	while(!q.empty())
		q.pop();

	for(long long i=1;i<=cnt*2;i++)
		del[i]=in[i]=false;

	sort(edge+1,edge+cnt+1);
	for(long long i=1;i<=cnt;i++) //处理第一行的前缀和
		sumfirst[i]=sumfirst[i-1]+edge[i].second;

	for(long long i=1;i<=cnt;i++)
		q.push(make_pair(edge[i].first-edge[i].second,i+cnt)); //第一行的标号为i,第二行的标号为i+cnt

	long long nowsum=0;
	for(long long i=1;i<=m-cnt;i++)
		nowsum += gettop();

	for(long long i=cnt;i>=0;i--) //[1,i]都取了第一行,这些列的决策都为“第二行”,[i+1,n]都不能取第二行,决策为“第一行”
	{ //要维护前m-i小的和
		if(i>m)
			continue;

		if(nowsum+sumfirst[i]<=k) //当前这个i是合法的
			return true;

		if(i+cnt<=m)
			return false;

		//更新nowsum
		q.push(make_pair(edge[i].second,i));
		nowsum += gettop();

		del[i+cnt]=true;
		if(in[i+cnt])
		{
			in[i+cnt]=false;
			nowsum -= edge[i].first-edge[i].second;
			nowsum += gettop();
		}
	}

	return false;
}

void add(long long x,long long y)
{
	edge[++cnt]=make_pair(x+y,x);
}

int max_score(int N, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W)
{
	n=N, x++, y++, cnt=0;
	for(long long i=1;i<=n;i++)
		g[i].clear(), w[i].clear(), inpath[i]=false, distx[i]=disty[i]=fat[i]=0;

	for(long long i=0;i<n-1;i++)
	{
		add(U[i]+1,V[i]+1,W[i]);
		add(V[i]+1,U[i]+1,W[i]);
	}

	dfsx(x,-1), dfsy(y,-1);
	for(long long i=1;i<=n;i++)
		g[i].clear();

	for(long long i=0;i<=n*2;i++)
		fa[i]=son[i]=del[i]=0;

	long long sum=0,cnt=0,ans=calc(k);
	for(long long i=y;i;i=fat[i])
	{
		inpath[i]=true;
		if(distx[i]>disty[i]) swap(distx[i],disty[i]);

		add(0,disty[i]-distx[i]);
		k -= distx[i], sum++;
		val[cnt+1].sum=disty[i]-distx[i];
		cnt++;
	}

	long long realk=k;
	if(k<0)
		return ans;

	for(long long i=1;i<=n;i++)
	{
		if(!inpath[i])
		{
			if(distx[i]>disty[i]) swap(distx[i],disty[i]);

			add(distx[i],disty[i]-distx[i]);
			val[cnt+2].sum=disty[i]-distx[i], val[cnt+1].sum=distx[i];
			fa[cnt+2]=cnt+1, son[cnt+1]=cnt+2;
			cnt += 2;
		}
	}

	priority_queue <node> q;
	for(long long i=1;i<=cnt;i++)
	{
		val[i].sz=1, val[i].id=i;
		q.push(val[i]), a[i]=val[i].sum;
	}

	while(!q.empty())
	{
		node x=q.top();
		q.pop();
		if(del[x.id])
			continue;

		if(!fa[x.id] || del[fa[x.id]])
		{
			if(k>=x.sum)
			{
				k -= x.sum;
				sum += x.sz;
				if(x.sz==1)
					del[x.id]=true;
				else
					del[x.id]=del[son[x.id]]=true;
				continue;
			}
			else
				break;
		}
		else
		{
			val[fa[x.id]].sz += val[x.id].sz, val[fa[x.id]].sum += x.sum;
			q.push(val[fa[x.id]]);
		}
	}

	for(long long i=1;;i++)
		if(!check(i,realk))
			return max(i-1,ans);
}

详细

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 93ms
memory: 72892kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
200000 31011 61157 8517583098
31011 129396 964383
1655 129396 331139
1655 191487 566483
110385 191487 865248
43212 110385 542661
43212 81682 13766
81682 91774 546589
91774 124706 780638
124706 175650 118706
10421 175650 615314
10421 151953 436270
140430 151...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
451

result:

ok 

Test #2:

score: 0
Accepted
time: 119ms
memory: 79336kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
200000 97133 170892 35489415917
114511 170892 730058
34783 114511 435023
34783 47301 562314
47301 162600 457629
44856 162600 365133
44856 133801 83016
117539 133801 124222
117539 128719 199821
77871 128719 703141
77871 133155 624331
7211 133155 138691
7211 ...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
650

result:

ok 

Test #3:

score: 0
Accepted
time: 39ms
memory: 44184kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
200
1000 611 992 5736784
504 611 954658
504 936 219278
502 936 632439
393 502 177662
267 393 570266
267 291 941365
291 310 168052
310 765 253098
635 765 724932
274 635 842125
274 799 848645
39 799 433118
39 940 705598
553 940 564063
553 960 69665
917 960 6904...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
126
38
69
34
52
33
42
32
39
41
38
36
45
84
40
44
50
42
47
34
38
47
38
37
39
37
44
39
32
33
38
54
25
36
46
33
37
35
28
36
45
43
44
49
37
33
43
44
53
42
33
30
50
41
37
40
37
44
207
31
37
45
36
43
35
40
41
39
135
53
40
32
31
37
34
38
51
48
36
40
48
42
43
43
3...

result:

ok 

Subtask #2:

score: 0
Wrong Answer

Test #4:

score: 9
Accepted
time: 3ms
memory: 41496kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
50 23 25 382806473
0 1 375710
1 2 898637
2 3 10402
3 4 536577
4 5 385023
5 6 71075
6 7 543368
7 8 301497
8 9 174394
9 10 711312
10 11 923006
11 12 675532
12 13 838667
13 14 565729
14 15 979816
15 16 862618
16 17 576015
17 18 177751
18 19 306989
19 20 881492...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
96

result:

ok 

Test #5:

score: -9
Wrong Answer
time: 1ms
memory: 42768kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
47 20 22 25669694
0 1 291237
1 2 851987
2 3 421247
3 4 962919
4 5 643085
5 6 224951
6 7 756890
7 8 147295
8 9 625823
9 10 736374
10 11 290526
11 12 335466
12 13 539086
13 14 957449
14 15 423408
15 16 932444
16 17 356032
17 18 307118
18 19 94279
19 20 989546...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
34

result:

wrong answer 1st lines differ - on the 1st token, expected: '26', found: '34'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #36:

score: 9
Accepted
time: 0ms
memory: 39868kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
4 0 1 9
0 2 2
1 2 3
2 3 3

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
6

result:

ok 

Test #37:

score: 0
Accepted
time: 1ms
memory: 39796kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
4 0 1 8
0 2 2
1 2 3
2 3 100

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
5

result:

ok 

Test #38:

score: 0
Accepted
time: 1ms
memory: 40620kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
8 0 4 84
0 1 1
1 2 29
2 3 29
3 4 1
4 5 20
2 6 20
3 7 1

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
9

result:

ok 

Test #39:

score: -9
Wrong Answer
time: 1ms
memory: 40836kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
18 14 15 221112
8 10 15984
3 8 2664
6 10 5328
9 10 13320
5 10 23976
1 10 13320
3 4 5328
3 7 26640
3 11 23976
4 15 23976
6 17 18648
12 17 5328
11 13 13320
0 11 7992
15 16 5328
2 16 5328
13 14 2664

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
15

result:

wrong answer 1st lines differ - on the 1st token, expected: '14', found: '15'

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #4:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%