oj.uz

Submission #1077224

# Submission time Handle Problem Language Result Execution time Memory
1077224 2024-08-27T03:29:46 Z pawned Petrol stations (CEOI24_stations) C++17
38 / 100
 3500 ms 2097152 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

const int MAX = 70005;

ll N, K;

vector<ii> adj[MAX];

vector<ll> subsz(MAX, 0);
vi par(MAX, -1);

void dfs(int n) {
	subsz[n] = 1;
	for (ii x : adj[n]) {
		if (subsz[x.fi] == 0) {
			dfs(x.fi);
			par[x.fi] = n;
			subsz[n] += subsz[x.fi];
		}
	}
}

int main() {
	fastIO();
	cin>>N>>K;
	for (int i = 0; i < N - 1; i++) {
		int u, v, w;	// w <= 1e9, can be int
		cin>>u>>v>>w;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}
	dfs(0);
/*	cout<<"subsz: ";
	for (int i = 0; i < N; i++) {
		cout<<subsz[i]<<" ";
	}
	cout<<endl;*/
	vi leaves;
	for (int i = 0; i < N; i++) {
		if (adj[i].size() == 1)
			leaves.pb(i);
	}
	map<ii, int> rem;
	for (int i = 0; i < N; i++) {
		for (ii p : adj[i]) {
			rem[{i, p.fi}] = adj[i].size() - 1;
		}
	}
/*	cout<<"rem: "<<endl;
	for (pair<ii, int> p : rem)
		cout<<"("<<p.fi.fi<<", "<<p.fi.se<<"): "<<p.se<<endl;*/
	vi base(K + 2, 0);
	base[K] = 1;
	base[K + 1] = 0;
	map<ii, vi> info;
	queue<ii> q;
	for (int x : leaves) {
		q.push({x, adj[x][0].fi});
		info[{x, adj[x][0].fi}] = base;
	}
	while (!q.empty()) {
		ii x = q.front();
		// {curr, next}
		q.pop();
		for (ii p : adj[x.se]) {
			// p is {vertex, dist}
			if (p.fi == x.fi)
				continue;
			// subtract 1 from rem
			// if rem becomes 0, push
			ii y = {x.se, p.fi};
			rem[y]--;
			if (rem[y] == 0) {
				vi toput = base;
				q.push(y);
				// calculate info for y
				// find all previous
				for (ii q : adj[x.se]) {
					if (q.fi == p.fi)
						continue;
					vi v = info[{q.fi, x.se}];
					for (int j = q.se; j <= K; j++) {	// need refill
						int arrive = j - q.se;
						if (arrive < p.se) {
							toput[K] += v[j];
							if (q.se == 0) {
								if (j != K)
									toput[K + 1] += v[j];
							}
							else {
								toput[K + 1] += v[j];
							}
						}
						else {
							toput[arrive] += v[j];
						}
					}
				}
				info[y] = toput;
			}
		}
	}
/*	cout<<"info: ";
	for (pair<ii, vi> p : info) {
		cout<<"("<<p.fi.fi<<", "<<p.fi.se<<"): ";
		for (int x : p.se)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<ll> ans(N, 0);
	for (pair<ii, vi> p : info) {
		ll pre = p.se[K + 1];	// number of refills, excluding start
		int x = p.fi.fi;
		int y = p.fi.se;
//		cout<<"at "<<x<<" "<<y<<endl;
		// going from x to y
		// ans[x] += (the size of y) times pre
		if (par[y] == x) {	// x is above y
			ans[x] += (subsz[y]) * pre;
//			cout<<"adding above "<<(subsz[y]) * pre<<endl;
		}
		else {	// y is above x
			ans[x] += (N - subsz[x]) * pre;
//			cout<<"adding below "<<(N - subsz[x]) * pre<<endl;
		}
	}
//	cout<<"ANSWER: ";
	for (ll x : ans)
		cout<<x<<" ";
	cout<<endl;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct
4 Correct 5 ms 5724 KB Output is correct
5 Correct 84 ms 10580 KB Output is correct
6 Correct 6 ms 6236 KB Output is correct
7 Correct 5 ms 5936 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 10 ms 9820 KB Output is correct
10 Correct 8 ms 9304 KB Output is correct
11 Correct 12 ms 11100 KB Output is correct
12 Correct 10 ms 11020 KB Output is correct
13 Correct 10 ms 11352 KB Output is correct
14 Correct 478 ms 7340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 230 ms 32336 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 230 ms 32336 KB Output is correct
5 Runtime error 716 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 244 ms 30032 KB Output is correct
4 Correct 278 ms 34136 KB Output is correct
5 Correct 242 ms 36432 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 246 ms 34900 KB Output is correct
8 Correct 259 ms 34896 KB Output is correct
9 Correct 274 ms 34900 KB Output is correct

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 244 ms 30032 KB Output is correct
4 Correct 278 ms 34136 KB Output is correct
5 Correct 242 ms 36432 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 246 ms 34900 KB Output is correct
8 Correct 259 ms 34896 KB Output is correct
9 Correct 274 ms 34900 KB Output is correct
10 Execution timed out 3566 ms 20688 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct
4 Correct 5 ms 5724 KB Output is correct
5 Correct 84 ms 10580 KB Output is correct
6 Correct 6 ms 6236 KB Output is correct
7 Correct 5 ms 5936 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 10 ms 9820 KB Output is correct
10 Correct 8 ms 9304 KB Output is correct
11 Correct 12 ms 11100 KB Output is correct
12 Correct 10 ms 11020 KB Output is correct
13 Correct 10 ms 11352 KB Output is correct
14 Correct 478 ms 7340 KB Output is correct
15 Correct 2 ms 2904 KB Output is correct
16 Correct 230 ms 32336 KB Output is correct
17 Runtime error 716 ms 2097152 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -