oj.uz

Submission #931803

# Submission time Handle Problem Language Result Execution time Memory
931803 2024-02-22T11:04:41 Z Wansur Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 341868 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

using namespace std;
typedef long long ll;
const int mx=3e3+12;

vector<pair<int,ll>> g[mx];
vector<int> ord;
ll dp2[4][mx][mx*2];
ll dp[4][mx][mx*2];
int sz2[mx];
ll cost1[mx];
ll cost2[mx];
ll tmp[4][mx];
bool is[mx];
int sz[mx];
ll n,k,x,y;

void init(){
	ord.clear();
	for(int i=0;i<n+10;i++){
		g[i].clear();
		cost1[i]=cost2[i]=0;
		is[i]=sz[i]=0;
		for(int j=0;j<n*2+10;j++){
			dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=dp[3][i][j]=1e18+1;
		}
	}
}

int calc(){
	vector<ll> a,b;
	int ans=0;
	for(int i=0;i<n;i++){
		a.push_back(cost1[i]);
		b.push_back(cost2[i]);
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	for(int i=1;i<n;i++){
		a[i]+=a[i-1];
	}
	for(int i=1;i<n;i++){
		b[i]+=b[i-1];
	}
	for(int i=0;i<n;i++){
		if(a[i]<=k || b[i]<=k){
			ans=max(ans,i+1);
		}
		for(int j=0;j<n;j++){
			if(a[i]+b[j]<=k){
				ans=max(ans,i+j+2);
			}
		}
	}
	return ans;
}

void calc(int v,int p,ll d[]){
	for(auto [to,w]:g[v]){
		if(to!=p){
			d[to]=d[v]+w;
			calc(to,v,d);
		}
	}
}

bool path(int v,int p,int f){
	if(v==f){
		ord.push_back(v);
		is[v]=1;
		return 1;
	}
	for(auto [to,w]:g[v]){
		if(to!=p && path(to,v,f)){
			ord.push_back(v);
			is[v]=1;
			return 1;
		}
	}
	return 0;
}

void dfs(int v,int p){
	dp[0][v][0]=0;
	dp[1][v][1]=cost1[v];
	dp[2][v][1]=cost2[v];
	dp[3][v][2]=max(cost1[v],cost2[v]);
	sz[v]=1;
	for(auto [to,w]:g[v]){
		if(to==p || is[to])continue;
		dfs(to,v);
		for(int m=0;m<4;m++){
			for(int i=0;i<=n*2;i++){
				tmp[m][i]=dp[m][v][i];
			}
		}
		for(int m=0;m<4;m++){
			for(int m1=m;m1>=0;m1=((m1-1)&m)){
				for(int x=0;x<=sz[v]*2;x++){
					for(int y=0;y<=sz[to]*2;y++){
						tmp[m][x+y]=min(tmp[m][x+y],dp[m][v][x]+dp[m1][to][y]);
					}
				}
				if(!m1)break;
			}
		}
		for(int m=0;m<4;m++){
			for(int i=0;i<=n*2;i++){
				dp[m][v][i]=tmp[m][i];
			}
		}
		sz[v]+=sz[to];
	}
}

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,x=X,y=Y;
	init();
	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]});
	}
	calc(x,-1,cost1);
	calc(y,-1,cost2);
	int ans=calc();
	path(y,-1,x);
	for(int i=ord.size()-1;i>=0;i--){
		dfs(ord[i],-1);
	}
	for(int i=0;i<n;i++){
		sz2[i]=sz[i];
	}
	for(int i=ord.size()-2;i>=0;i--){
		int v=ord[i],u=ord[i+1];
		for(int m=2;m<4;m++){
			for(int i=0;i<n*2+10;i++){
				tmp[m][i]=1e18+1;
			}
		}
		for(int m=2;m<4;m++){
			for(int m1=m;m1>1;m1=((m1-1)&m)){
				for(int x=1;x<=sz[v]*2;x++){
					for(int y=1;y<=sz[u]*2;y++){
						tmp[m][x+y]=min(tmp[m][x+y],dp[m][v][x]+dp[m1][u][y]);
					}
				}
			}
		}
		for(int m=2;m<4;m++){
			for(int i=0;i<n*2+10;i++){
				dp[m][v][i]=tmp[m][i];
			}
		}
		sz[v]+=sz[u];
	}
	for(int i=0;i<ord.size()-1;i++){
		int u=ord[i],v=ord[i+1];
		for(int m=0;m<2;m++){
			for(int i=0;i<n*2+10;i++){
				tmp[m][i]=1e18+1;
			}
		}
		int m=1,m1=1;
		for(int x=1;x<=sz2[v]*2;x++){
			for(int y=1;y<=sz2[u]*2;y++){
				tmp[m][x+y]=min(tmp[m][x+y],dp[m][v][x]+dp[m1][u][y]);
			}	
		}
		for(int m=1;m<2;m++){
			for(int i=0;i<n*2+10;i++){
				dp[m][v][i]=tmp[m][i];
			}
		}
		sz2[v]+=sz2[u];
	}
	for(int i=0;i<n;i++){
		for(int j=n*2-1;j>=0;j--){
			dp[3][i][j]=min(dp[3][i][j+1],dp[3][i][j]);
			dp[1][i][j]=min(dp[1][i][j+1],dp[1][i][j]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<=n*2;j++){
			if(dp[3][x][j]<=k){
				ans=max(ans,j);
			}
		}
	}
	for(int i=0;i<ord.size()-1;i++){
		int v=ord[i],u=ord[i+1];
		int j=0;
		for(int i=n*2;i>=0;i--){
			while(j<n*2 && dp[3][u][j+1]+dp[1][v][i]<=k){
				j++;
			}
			if(dp[3][u][j]+dp[1][v][i]<=k){
				ans=max(ans,i+j);
			}
		}
		break;
	}
	return ans;
}

Compilation message

closing.cpp: In function 'void init()':
closing.cpp:27:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |   is[i]=sz[i]=0;
      |         ~~~~~^~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:160:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |  for(int i=0;i<ord.size()-1;i++){
      |              ~^~~~~~~~~~~~~
closing.cpp:193:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |  for(int i=0;i<ord.size()-1;i++){
      |              ~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 341868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Incorrect 2 ms 12808 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
6 Halted 0 ms 0 KB -