Submission #1046164

#TimeUsernameProblemLanguageResultExecution timeMemory
1046164VahanAbrahamPetrol stations (CEOI24_stations)C++17
0 / 100
1 ms2652 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <algorithm> #include <cstring> #include <cstdio> #include <sstream> #include <map> #include <stack> #include <set> #include <queue> #include <list> #include <unordered_set> #include <unordered_map> #include <math.h> #include <bitset> #include <cmath> #include <vector> #include <iomanip> #include <random> #include <chrono> #include <cassert> using namespace std; #define ll long long #define fr first #define sc second #define pb push_back #define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout); ll gcd(ll a, ll b) { if (a == 0 || b == 0) { return max(a, b); } if (a <= b) { return gcd(a, b % a); } else { return gcd(a % b, b); } } ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; } const int N = 70005; const ll oo = 100000000000000000, MOD = 1000000007; ll cnt[N], ans[N], pat[N]; int n, k, sz[N], a[N], last = 1; vector<pair<int, int>> g[N]; void dfs(int u, int p) { //cout << u << endl; a[last] = u; ++last; for (int i = 0; i < g[u].size(); ++i) { int h = g[u][i].fr; int w = g[u][i].sc; if (h != p) { dfs(h, u); } } } void solve() { cin >> n >> k; for (int i = 1; i <= n - 1; ++i) { int u, v, w; cin >> u >> v >> w; g[u].pb({ v,w }); g[v].pb({ u,w }); } for (int i = 0; i < n; ++i) { if (g[i].size() == 1) { last = 1; dfs(i, -1); break; } } for (int i = 1; i <= n; ++i) { ans[i] = 1; if (i - k >= 1) { ans[i] += ans[i - k]; } pat[a[i]] += (ans[i] - 1) * (n - i + 1); } for (int i = n; i >= 1; --i) { ans[i] = 1; if (n - i >= k) { ans[i] += ans[i + k]; } pat[a[i]] += (ans[i] - 1) * (i); } for (int i = 0; i < n; ++i) { cout << pat[i] << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //US int tt = 1; //cin >> tt; while (tt--) { solve(); } }

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < g[u].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:62:13: warning: unused variable 'w' [-Wunused-variable]
   62 |         int w = g[u][i].sc;
      |             ^
#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...