Submission #1077160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077160		pawned	Petrol stations (CEOI24_stations)	C++17	8 / 100	24 ms	6876 KiB

Main

#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];

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});
	}
	int start = -1;
	for (int i = 0; i < N; i++) {
		if (adj[i].size() == 1)
			start = i;
	}
	vi order;
	vector<bool> vis(N, false);
	queue<int> q;
	q.push(start);
	vis[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		order.pb(x);
		for (ii y : adj[x]) {
			if (!vis[y.fi]) {
				vis[y.fi] = true;
				q.push(y.fi);
			}
		}
	}
/*	cout<<"order: ";
	for (int x : order)
		cout<<x<<" ";
	cout<<endl;*/
	vector<ll> ans(N, 0);
	for (ll i = 0; i < N; i++) {
		ans[order[i]] = (i / K) * (N - 1 - i) + ((N - 1 - i) / K) * i;
	}
//	cout<<"ANSWER: ";
	for (ll x : ans)
		cout<<x<<" ";
	cout<<endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 18
• Subtask 2: 8 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35