oj.uz

답안 #917086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917086 2024-01-27T06:39:50 Z penguin133 Truck Driver (IOI23_deliveries) C++17
22 / 100
 5500 ms 25328 KB 
#include <bits/stdc++.h>
using namespace std;

#include "deliveries.h"
//#define int long long
typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector <int> t, w, u, v;
ll dist[300005];

struct node{
	int s, e, m; ll val, val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		val = val2 = 0;
	}
	
	void upd(int p, ll v){
		if(s == e){
			val = v;
			val2 = v * dist[p];
			return;
		}
		if(p <= m)l->upd(p, v);
		else r->upd(p, v);
		val = l->val + r->val;
		val2 = l->val2 + r->val2;
	}
	
	pi qry(int a, int b){
		if(a > b)return {0, 0};
		if(s == a && b == e)return {val,val2};
		if(b <= m)return l->qry(a, b);
		if(a > m)return r->qry(a ,b);
		pi lft = l->qry(a, m), rgt = r->qry(m+1, b);
		return {lft.fi + rgt.fi, lft.se + rgt.se};
	}
}*root;
ll n, sm, par[100005], shit[100005], tot[100005], cnt = 0;
vector <pi> adj[100005];
void dfs(int x, ll cur){
	dist[x] = cur;
	tot[x] = w[x], shit[x] = dist[x] * w[x];
	for(auto [i, j] : adj[x]){
		par[i] = x;
		dfs(i, cur + j);
		tot[x] += tot[i];
		shit[x] += shit[i];
	}
}
/*
int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int df = dep[v] - dep[u];
	for(int i = 0; i <= 19; i++)if(df >> i & 1)v = par[i][v];
	if(u == v)return u;
	for(int i = 19; i >= 0; i--)if(par[i][u] != par[i][v])u = par[i][u], v = par[i][v];
	return par[0][u];
}
*/

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	u = U; v = V; t = T; w = W;
	for(int i = 0; i < N - 1; i++)adj[U[i]].push_back({V[i], T[i]});
	dfs(0, 0);
	//for(int i = 0; i < N; i++)back[S[i]] = i;
	//for(int i = 1; i < N; i++)dist[i] = dist[i - 1] + t[i - 1];
	//root = new node(0, N - 1);
	n = N;
	//for(int i = 0; i < N; i++)root->upd(i, w[i]), sm += w[i];
	return;
}

long long max_time(int S, int X) {
	
	int tmp = S;
	while(1){
		tot[tmp] += X - w[S];
		shit[tmp] += (X - w[S]) * dist[S];
		if(!tmp)break;
		tmp = par[tmp];
	}
	w[S] = X;
	ll bruh = 0, ext = 0, cur = 0;
	while(1){
		ext += w[bruh];
		if(adj[bruh].empty()){
			cur += 2 * dist[bruh];
			break;
		}
		ll brr = 0, mx = 0;
		
		//ll x = bruh * 2 + 1, y = bruh * 2 + 2;
		for(auto [i, j] : adj[bruh])brr += tot[i], mx = max(mx, tot[i]);
		if(mx - ext > brr - mx){
			ll bruh2 = 0;
			for(auto [i, j] : adj[bruh])bruh2 += shit[i];
			for(auto [i, j] : adj[bruh]){
				if(tot[i] == mx){
					bruh2 -= shit[i];
					cur += (bruh2 - (brr - mx) * dist[bruh]) * 2;
					cur += j * 2 * (brr - mx + ext);
					ext += brr - mx;
					bruh = i;
					break;
				}
			}
		}
		else{
			brr = 0; ll brr2 = 0;
			for(auto [i, j] : adj[bruh])brr += shit[i], brr2 += tot[i];
			cur += (brr - brr2 * dist[bruh]) * 2 + 2 * dist[bruh];
			break;
		}
		/*
		if(tot[x] > tot[y]){
			cur += (shit[y] - tot[y] * dist[bruh]) * 2;
			cur += adj[bruh][0].se * 2 * (tot[y] + ext);
			ext += tot[y];
			bruh = x;
		}
		else{
			cur += (shit[x] - tot[x] * dist[bruh]) * 2;
			cur += adj[bruh][1].se * 2 * (tot[x] + ext);
			ext += tot[x];
			bruh = y;
		}
		*/
	}
	return cur;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 14040 KB Output is correct
2 Correct 70 ms 13728 KB Output is correct
3 Correct 71 ms 14160 KB Output is correct
4 Correct 77 ms 13984 KB Output is correct
5 Correct 72 ms 14156 KB Output is correct

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 5 ms 6784 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 6 ms 7000 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 5 ms 6812 KB Output is correct
9 Correct 6 ms 6948 KB Output is correct
10 Correct 7 ms 6952 KB Output is correct
11 Correct 3 ms 6744 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Incorrect 2 ms 6748 KB 3rd lines differ - on the 1st token, expected: '63174', found: '0'
15 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 14040 KB Output is correct
2 Correct 70 ms 13728 KB Output is correct
3 Correct 71 ms 14160 KB Output is correct
4 Correct 77 ms 13984 KB Output is correct
5 Correct 72 ms 14156 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 4 ms 7000 KB Output is correct
8 Correct 17 ms 8216 KB Output is correct
9 Correct 200 ms 20020 KB Output is correct
10 Correct 203 ms 20020 KB Output is correct
11 Correct 194 ms 19860 KB Output is correct
12 Correct 135 ms 21296 KB Output is correct
13 Correct 136 ms 21412 KB Output is correct
14 Correct 134 ms 21400 KB Output is correct

Subtask #4
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 14040 KB Output is correct
2 Correct 70 ms 13728 KB Output is correct
3 Correct 71 ms 14160 KB Output is correct
4 Correct 77 ms 13984 KB Output is correct
5 Correct 72 ms 14156 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 16 ms 6748 KB Output is correct
8 Correct 1359 ms 9048 KB Output is correct
9 Execution timed out 5537 ms 25328 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 14040 KB Output is correct
2 Correct 70 ms 13728 KB Output is correct
3 Correct 71 ms 14160 KB Output is correct
4 Correct 77 ms 13984 KB Output is correct
5 Correct 72 ms 14156 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 5 ms 6784 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 5 ms 6748 KB Output is correct
11 Correct 6 ms 7000 KB Output is correct
12 Correct 4 ms 6748 KB Output is correct
13 Correct 5 ms 6812 KB Output is correct
14 Correct 6 ms 6948 KB Output is correct
15 Correct 7 ms 6952 KB Output is correct
16 Correct 3 ms 6744 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Incorrect 2 ms 6748 KB 3rd lines differ - on the 1st token, expected: '63174', found: '0'
20 Halted 0 ms 0 KB -