제출 #1077136

#제출 시각아이디문제언어결과실행 시간메모리
1077136pawnedPetrol stations (CEOI24_stations)C++17
18 / 100
1494 ms8580 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...