Task: | Tietoverkko |
Sender: | xenial |
Submission time: | 2021-10-07 18:12:44 +0300 |
Language: | C++17 |
Status: | READY |
Result: | 25 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | ACCEPTED | 15 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.93 s | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
Compiler report
input/code.cpp: In function 'void set_io(std::__cxx11::string)': input/code.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen((filename + ".in").c_str(), "r", stdin); ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen((filename + ".out").c_str(), "w", stdout); ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(x) (x).begin(), (x).end() #define pb push_back #define fi first #define se second #define sz size #define rsz resize void set_io(string filename = "") { ios::sync_with_stdio(0); cin.tie(0); if (filename != "") { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } } int LOG = 0; vector<vector<pair<int,int>>> adj; vector<int> depth; vector<vector<int>> anc, bw; void dfs(int a = 0, int l = -1, int d = 0) { depth[a] = d; anc[a][0] = l; if (l != -1) { for (auto n : adj[a]) if (n.fi == l) bw[a][0] = n.se; } for (int i = 1; i < LOG; i++) { if (anc[a][i - 1] != -1) { anc[a][i] = anc[anc[a][i - 1]][i - 1]; bw[a][i] = min(bw[a][i - 1], bw[anc[a][i - 1]][i - 1]); } } for (auto n : adj[a]) { if (n.fi == l) continue; depth[n.fi] = d; anc[n.fi][0] = a; bw[n.fi][0] = n.se; dfs(n.fi, a, d + 1); } } int getbw(int a, int b) { int ans = INT_MAX; if (depth[a] > depth[b]) swap(a, b); if (depth[a] < depth[b]) { int diff = depth[b] - depth[a]; for (int i = LOG - 1; i >= 0; i--) { if (diff & (1 << i)) { if (bw[b][i]) ans = min(ans, bw[b][i]); b = anc[b][i]; } } } if (a == b) return ans; for (int i = LOG - 1; i >= 0; i--) { if (anc[a][i] != anc[b][i]) { ans = min({ans, bw[a][i], bw[b][i]}); a = anc[a][i]; b = anc[b][i]; } } return min({ans, bw[a][0], bw[b][0]}); } int main() { set_io(); //set_io("C:\\Users\\maste\\OneDrive\\Programming\\learning\\tverkko"); int n; cin >> n; adj.rsz(n); depth.rsz(n); for (int i = 0; i < n-1; i++) { int a, b, x; cin >> a >> b >> x; adj[a-1].pb({b-1, x}); adj[b-1].pb({a-1, x}); } while (1 << (LOG + 1) <= n) LOG++; bw = anc = vector<vector<int>>(n, vector<int>(LOG)); dfs(); ll ans = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) ans += getbw(i, j); cout << ans << endl; }
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 1 2 74 1 3 100 2 4 50 3 5 40 ... |
correct output |
---|
88687 |
user output |
---|
88687 |
Test 2
Group: 2, 3
Verdict: ACCEPTED
input |
---|
5000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1103702320243776 |
user output |
---|
1103702320243776 |
Test 3
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1080549209850010931 |
user output |
---|
(empty) |