이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |