oj.uz

Submission #1068602

# Submission time Handle Problem Language Result Execution time Memory
1068602 2024-08-21T10:54:10 Z jamjanek Truck Driver (IOI23_deliveries) C++17
8 / 100
 69 ms 10124 KB 
#include "deliveries.h"
#include<bits/stdc++.h>
using namespace std;
int n, i;
vector<pair<int,long long>>graf[100010];
vector<int>val;
long long dep[100010];
long long r[100010];
long long pom[100010];

void dfs1(int x, int o){
	r[x]=val[x];
	pom[x]=val[x]*dep[x];
	for(auto j: graf[x])
		if(j.first!=o){
			dfs1(j.first, x);
			r[x]+=r[j.first];
			pom[x]+=pom[j.first];
		}
}

void dfs0(int x, int o){
	for(auto j: graf[x])
		if(j.first!=o){
			dep[j.first]=dep[x]+j.second;
			dfs0(j.first,x);
		}
}
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	n=N;
	for(i=0;i<n-1;i++)
		graf[U[i]].push_back({V[i], T[i]}),
		graf[V[i]].push_back({U[i], T[i]});
	val = W;
	dfs0(0,0);
	dfs1(0,0);
	return;
}

long long wynik;//suma lca dwoch kolejnych w ciagu

void dfs2(int x, int o, long long usu){
//	printf("%d: przed %lld  %d\n", x, wynik, usu);
	pair<long,long> best{-1,-1};
	for(auto j: graf[x]){
		if(j.first!=o)
			best=max(best, {r[j.first],j.first});
	}
	if(best.first==-1){
//		if(x==3)printf("  %lld\n", max(0ll, r[x]-usu-1));
		wynik+=dep[x]*2*max(0ll, r[x]-usu-1);
		return;
	}
	if(r[x]-best.first+usu+1>=best.first){
		wynik+=dep[x]*2*(max(0ll,r[x]-usu-1));
		return;
	}
//	wynik-=(r[x]-usu)*dep[x]*2;
	for(auto j: graf[x])
		if(j.first==best.second){
			dfs2(j.first,x, usu+r[x]-best.first);
		}
//	printf("%d: po %lld\n", x, wynik);
}

long long max_time(int S, int X) {
//	printf("pytanie\n");
	val[S] = X;
	wynik = 0;
	dfs1(0,0);
//	for(i=0;i<n;i++)printf("%d %lld %lld %lld\n", i, dep[i], r[i], pom[i]);
	dfs2(0,0,0);
	return pom[0]*2-wynik;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10068 KB Output is correct
2 Correct 62 ms 9864 KB Output is correct
3 Correct 62 ms 10064 KB Output is correct
4 Correct 57 ms 10068 KB Output is correct
5 Correct 60 ms 10124 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2908 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '4052724'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10068 KB Output is correct
2 Correct 62 ms 9864 KB Output is correct
3 Correct 62 ms 10064 KB Output is correct
4 Correct 57 ms 10068 KB Output is correct
5 Correct 60 ms 10124 KB Output is correct
6 Incorrect 1 ms 2908 KB 3rd lines differ - on the 1st token, expected: '45306', found: '59282'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10068 KB Output is correct
2 Correct 62 ms 9864 KB Output is correct
3 Correct 62 ms 10064 KB Output is correct
4 Correct 57 ms 10068 KB Output is correct
5 Correct 60 ms 10124 KB Output is correct
6 Incorrect 1 ms 2908 KB 3rd lines differ - on the 1st token, expected: '129238', found: '221794'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10068 KB Output is correct
2 Correct 62 ms 9864 KB Output is correct
3 Correct 62 ms 10064 KB Output is correct
4 Correct 57 ms 10068 KB Output is correct
5 Correct 60 ms 10124 KB Output is correct
6 Incorrect 2 ms 2908 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '4052724'
7 Halted 0 ms 0 KB -