Submission #1077136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077136		pawned	Petrol stations (CEOI24_stations)	C++17	18 / 100	1494 ms	8580 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 = 1005;

int N, K;

vector<ii> adj[MAX];

vector<vi> adjc(MAX, vi(MAX, 1e9));

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});
		adjc[u][v] = w;
		adjc[v][u] = w;
	}
	vector<vi> par(N, vi(N, -1));
	// par[i][j]: parent of j leading to i
	for (int i = 0; i < N; i++) {
		queue<int> q;
		par[i][i] = i;
		q.push(i);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (ii y : adj[x]) {
				if (par[i][y.fi] == -1) {
					par[i][y.fi] = x;
					q.push(y.fi);
				}
			}
		}
	}
/*	cout<<"par: "<<endl;
	for (vi v : par) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vi cnt(N, 0);	// number of refuel at each station
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
//			cout<<"doing "<<i<<" "<<j<<endl;
			int rem = K;
			int curr = i;
			while (curr != j) {
//				cout<<"at "<<curr<<endl;
				// go to par[j][curr]
				if (rem >= adjc[curr][par[j][curr]]) {
					rem -= adjc[curr][par[j][curr]];
				}
				else {
					cnt[curr]++;
//					cout<<"refueled at "<<curr<<endl;
					rem = K - adjc[curr][par[j][curr]];
				}
//				cout<<"remaining: "<<rem<<endl;
				curr = par[j][curr];
			}
		}
	}
//	cout<<"ANSWER: ";
	for (int x : cnt)
		cout<<x<<" ";
	cout<<endl;
}

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