Submission #854467

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854467	2023-09-27T17:15:07 Z	Wansur	Closing Time (IOI23_closing)	C++17	9 / 100	1000 ms	32636 KB

closing

#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second

using namespace std;
const int mx=2e5+12;

vector<pair<int,long long>> g[mx];
long long d[mx];
long long d1[mx];
long long d2[mx];
int p1[mx];
int p2[mx];
int A[mx];
long long n,k;
bool ok=0;

void dfs1(int v,int p,int d,int mask){
	d=min(d,A[v]);
	if(!d && A[v]){
		ok=1;
	}
	for(auto To:g[v]){
		if(To.f!=p){
			dfs1(To.f,v,d,mask);
		}
	}
}

void dfs(int v,int p,bool ok){
	for(auto To:g[v]){
		int to=To.f,w=To.s;
		if(to==p){
			continue;
		}
		if(ok){
			d2[to]=d2[v]+w;
		}
		else{
			d1[to]=d1[v]+w;
		}
		dfs(to,v,ok);
	}
}

int max_score(int N, int x, int y, long long K, std::vector<int> U,std::vector<int> V, std::vector<int> W){
	n=N,k=K;
	for(int i=0;i<n;i++){
		g[i].clear();
		d1[i]=d2[i]=0;
	}
	bool ok=1;
	for(int i=0;i<n-1;i++){
		if(!(U[i]==i && V[i]==i+1)){
			ok=0;
		}
		g[V[i]].push_back({U[i],W[i]});
		g[U[i]].push_back({V[i],W[i]});
	}
	if(ok){
		dfs(x,-1,0);
		dfs(y,-1,1);
		long long ans=0;
		for(int l1=x;l1>=0;l1--){
			for(int r1=x;r1<n;r1++){
				for(int l2=y;l2>=0;l2--){
					for(int r2=y;r2<n;r2++){
						long long sum=0,cnt=0;
						for(int i=0;i<n;i++){
							long long t=0;
							if(l1<=i && i<=r1){
								t=d1[i];
								cnt++;
							}
							if(l2<=i && i<=r2){
								t=max(t,d2[i]);
								cnt++;
							}
							sum+=t;
						}
						if(sum<=k){
							ans=max(ans,cnt);
						}
					}
				}
			}
		}
		long long cnt=0,sum=0;
		vector<long long> v;
		for(int i=0;i<n;i++){
			v.push_back(d1[i]);
		}
		sort(v.begin(),v.end());
		for(long long x:v){
			if(sum+x<=k){
				sum+=x;
				cnt++;
			}
		}
		ans=max(ans,cnt);
		cnt=sum=0;
		v.clear();
		for(int i=0;i<n;i++){
			v.push_back(d2[i]);
		}
		sort(v.begin(),v.end());
		for(long long x:v){
			if(sum+x<=k){
				sum+=x;
				cnt++;
			}
		}
		ans=max(ans,cnt);
		return ans;
	}
	dfs(x,-1,0);
	dfs(y,-1,1);
	vector<int> a,b;
	for(int mask=0;mask<(1<<n);mask++){
		for(int i=0;i<n;i++){
			A[i]=0;
			if((mask&(1<<i))){
				A[i]=1;
			}
		}
		ok=0;
		dfs1(x,-1,1,mask);
		if(!ok){
			a.push_back(mask);
		}
		ok=0;
		dfs1(y,-1,1,mask);
		if(!ok){
			b.push_back(mask);
		}
	}
	int ans=0;
	for(int x:a){
		for(int y:b){
			long long sum=0;
			int cnt=0;
			for(int i=0;i<n;i++){
				long long t=0;
				if(((1<<i)&x)){
					t=d1[i];
					cnt++;
				}
				if(((1<<i)&y)){
					t=max(t,d2[i]);
					cnt++;
				}
				sum+=t;
			}
			if(sum<=k){
				ans=max(ans,cnt);
			}
		}
	}
	return ans;
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7768 KB	Output is correct

Subtask #1
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	109 ms	32636 KB	1st lines differ - on the 1st token, expected: '451', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	3 ms	7772 KB	Output is correct
3	Correct	2 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	44 ms	7772 KB	Output is correct
7	Correct	32 ms	7768 KB	Output is correct
8	Correct	12 ms	7772 KB	Output is correct
9	Correct	3 ms	7900 KB	Output is correct
10	Correct	2 ms	7772 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct

Subtask #3
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	3 ms	7772 KB	Output is correct
3	Correct	2 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	44 ms	7772 KB	Output is correct
7	Correct	32 ms	7768 KB	Output is correct
8	Correct	12 ms	7772 KB	Output is correct
9	Correct	3 ms	7900 KB	Output is correct
10	Correct	2 ms	7772 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	139 ms	7888 KB	Output is correct
13	Correct	86 ms	7884 KB	Output is correct
14	Correct	292 ms	7888 KB	Output is correct
15	Correct	120 ms	7772 KB	Output is correct
16	Correct	3 ms	7768 KB	Output is correct
17	Correct	3 ms	7768 KB	Output is correct
18	Correct	12 ms	7772 KB	Output is correct
19	Execution timed out	1010 ms	7768 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	3 ms	7772 KB	Output is correct
3	Correct	2 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	44 ms	7772 KB	Output is correct
7	Correct	32 ms	7768 KB	Output is correct
8	Correct	12 ms	7772 KB	Output is correct
9	Correct	3 ms	7900 KB	Output is correct
10	Correct	2 ms	7772 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	139 ms	7888 KB	Output is correct
13	Correct	86 ms	7884 KB	Output is correct
14	Correct	292 ms	7888 KB	Output is correct
15	Correct	120 ms	7772 KB	Output is correct
16	Correct	3 ms	7768 KB	Output is correct
17	Correct	3 ms	7768 KB	Output is correct
18	Correct	12 ms	7772 KB	Output is correct
19	Execution timed out	1010 ms	7768 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	3 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	2 ms	7772 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	5 ms	7768 KB	Output is correct
10	Execution timed out	1100 ms	9988 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	3 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	44 ms	7772 KB	Output is correct
8	Correct	32 ms	7768 KB	Output is correct
9	Correct	12 ms	7772 KB	Output is correct
10	Correct	3 ms	7900 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	139 ms	7888 KB	Output is correct
14	Correct	86 ms	7884 KB	Output is correct
15	Correct	292 ms	7888 KB	Output is correct
16	Correct	120 ms	7772 KB	Output is correct
17	Correct	3 ms	7768 KB	Output is correct
18	Correct	3 ms	7768 KB	Output is correct
19	Correct	2 ms	7772 KB	Output is correct
20	Correct	2 ms	7772 KB	Output is correct
21	Correct	5 ms	7768 KB	Output is correct
22	Execution timed out	1100 ms	9988 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	3 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	44 ms	7772 KB	Output is correct
8	Correct	32 ms	7768 KB	Output is correct
9	Correct	12 ms	7772 KB	Output is correct
10	Correct	3 ms	7900 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	139 ms	7888 KB	Output is correct
14	Correct	86 ms	7884 KB	Output is correct
15	Correct	292 ms	7888 KB	Output is correct
16	Correct	120 ms	7772 KB	Output is correct
17	Correct	3 ms	7768 KB	Output is correct
18	Correct	3 ms	7768 KB	Output is correct
19	Correct	12 ms	7772 KB	Output is correct
20	Execution timed out	1010 ms	7768 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	3 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	44 ms	7772 KB	Output is correct
8	Correct	32 ms	7768 KB	Output is correct
9	Correct	12 ms	7772 KB	Output is correct
10	Correct	3 ms	7900 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	139 ms	7888 KB	Output is correct
14	Correct	86 ms	7884 KB	Output is correct
15	Correct	292 ms	7888 KB	Output is correct
16	Correct	120 ms	7772 KB	Output is correct
17	Correct	3 ms	7768 KB	Output is correct
18	Correct	3 ms	7768 KB	Output is correct
19	Correct	12 ms	7772 KB	Output is correct
20	Execution timed out	1010 ms	7768 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7768 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	3 ms	7772 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7772 KB	Output is correct
7	Correct	44 ms	7772 KB	Output is correct
8	Correct	32 ms	7768 KB	Output is correct
9	Correct	12 ms	7772 KB	Output is correct
10	Correct	3 ms	7900 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	139 ms	7888 KB	Output is correct
14	Correct	86 ms	7884 KB	Output is correct
15	Correct	292 ms	7888 KB	Output is correct
16	Correct	120 ms	7772 KB	Output is correct
17	Correct	3 ms	7768 KB	Output is correct
18	Correct	3 ms	7768 KB	Output is correct
19	Correct	12 ms	7772 KB	Output is correct
20	Execution timed out	1010 ms	7768 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Submission #854467

Compilation message