oj.uz

Submission #854448

# Submission time Handle Problem Language Result Execution time Memory
854448 2023-09-27T16:42:45 Z Wansur Closing Time (IOI23_closing) C++17
0 / 100
 600 ms 31572 KB 
#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];
int n,k;
bool ok=0;

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){
			p2[to]=v;
			d2[to]=d2[v]+w;
		}
		else{
			p1[to]=v;
			d1[to]=d1[v]+w;
		}
		dfs(to,v,ok);
	}
}

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);
		}
	}
}

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;
		p1[i]=p2[i]=-1;
	}
	for(int i=0;i<n-1;i++){
		g[V[i]].push_back({U[i],W[i]});
		g[U[i]].push_back({V[i],W[i]});
	}
	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 9820 KB Output is correct

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 297 ms 9920 KB Output is correct
3 Correct 351 ms 9932 KB Output is correct
4 Correct 313 ms 9820 KB Output is correct
5 Correct 155 ms 9928 KB Output is correct
6 Incorrect 196 ms 9932 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 297 ms 9920 KB Output is correct
3 Correct 351 ms 9932 KB Output is correct
4 Correct 313 ms 9820 KB Output is correct
5 Correct 155 ms 9928 KB Output is correct
6 Incorrect 196 ms 9932 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 297 ms 9920 KB Output is correct
3 Correct 351 ms 9932 KB Output is correct
4 Correct 313 ms 9820 KB Output is correct
5 Correct 155 ms 9928 KB Output is correct
6 Incorrect 196 ms 9932 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 297 ms 9920 KB Output is correct
4 Correct 351 ms 9932 KB Output is correct
5 Correct 313 ms 9820 KB Output is correct
6 Correct 155 ms 9928 KB Output is correct
7 Correct 2 ms 9816 KB Output is correct
8 Correct 2 ms 9924 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 137 ms 10332 KB Output is correct
11 Correct 600 ms 9984 KB Output is correct
12 Correct 14 ms 9816 KB Output is correct
13 Correct 368 ms 9820 KB Output is correct
14 Incorrect 222 ms 9820 KB 1st lines differ - on the 1st token, expected: '38', found: '0'
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 297 ms 9920 KB Output is correct
4 Correct 351 ms 9932 KB Output is correct
5 Correct 313 ms 9820 KB Output is correct
6 Correct 155 ms 9928 KB Output is correct
7 Incorrect 196 ms 9932 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 297 ms 9920 KB Output is correct
4 Correct 351 ms 9932 KB Output is correct
5 Correct 313 ms 9820 KB Output is correct
6 Correct 155 ms 9928 KB Output is correct
7 Incorrect 196 ms 9932 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 297 ms 9920 KB Output is correct
4 Correct 351 ms 9932 KB Output is correct
5 Correct 313 ms 9820 KB Output is correct
6 Correct 155 ms 9928 KB Output is correct
7 Incorrect 196 ms 9932 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 297 ms 9920 KB Output is correct
4 Correct 351 ms 9932 KB Output is correct
5 Correct 313 ms 9820 KB Output is correct
6 Correct 155 ms 9928 KB Output is correct
7 Incorrect 196 ms 9932 KB 1st lines differ - on the 1st token, expected: '96', found: '0'
8 Halted 0 ms 0 KB -