Task: | Tietoverkko |
Sender: | Sahari Kempo |
Submission time: | 2021-10-17 15:00:57 +0300 |
Language: | C++17 |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | TIME LIMIT EXCEEDED | -- | 1, 2, 3 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
#include <math.h> #include <iostream> #include <map> #include <vector> #define L long long using namespace std; void definef(); vector<L> erittely(L k); pair<L,L> ylos(L a, L k); pair<L, L> ylos(L a, L k, L c); L f(L x, L k); L etsi(L a, L b); map<L, pair<pair<L, L>, L>> m = { {1, { {0, 0}, 1 }} }; map<L, map<L, pair<L, L>>> fx; L n; int main() { L a, b, x, k = 0; cin >> n; L kerros = 1; L e = 0; for (L i = 0; i < n - 1; i++) { cin >> a >> b >> x; if (a < e) kerros = m[a].second; e = b; kerros++; m[b] = { {a, x}, kerros }; } definef(); for (L i = 1; i < n; i++) { k += etsi(i, n); if (n - i > 1) k += etsi(n - i, 1); if(i + 1 < n - i) k += etsi(i + 1, n - i); } cout << k << "\n"; } void definef() { for (L i = 1; i <= n; i *= 2) { for (L j = 1 + i; j <= n; j++) { pair<L,L> p = ylos(j, i); fx[i][j] = p; } } } vector<L> erittely(L k) { vector<L> komponentit; L sum = 0; L i = 0; L kom = 0; while (true) { kom = powl(2, i); if (kom > k) { kom = powl(2, i - 1); komponentit.push_back(kom); sum = kom; break; } else if (kom == k) { komponentit.push_back(kom); sum = kom; break; } i++; } while (sum != k) { kom = kom / 2; if (kom + sum <= k) { kom *= 2; komponentit.push_back(kom); sum += kom; } } return komponentit; } pair<L,L> ylos(L a, L k) { L minx = 1000000000; for (L i = 0; i < k; i++) { if (a == 1) break; if (minx == 1) break; if (m[a].first.second < minx) minx = m[a].first.second; a = m[a].first.first; } if (minx == 1000000000) { pair<L, L> p = { a, 0 }; return p; } pair<L, L> p = { a, minx }; return p; } pair<L, L> ylos(L a, L k, L c) { L minx = 1000000000; for (L i = 0; i < k; i++) { if (a == 1) break; if (minx == 1) break; if (m[a].first.second < minx) minx = m[a].first.second; a = m[a].first.first; } if (c < minx) minx = c; if (minx == 1000000000) { pair<L, L> p = { a, 0 }; return p; } pair<L, L> p = { a, minx }; return p; } L f(L x, L k) { vector<L> komponentit = erittely(k); L c = 0; for (auto kom : komponentit) { c = fx[kom][x].second; if (fx[kom][x].first == 1 || c == 1) break; x = fx[kom][x].first; } return c; } L etsi(L a, L b) { L c = 1000000000, c2 = 1000000000, d = m[a].second - m[b].second; if (d < 0) c2 = f(b, -d); else if (d > 0) c = f(a, d); if (a == b) { c = m[a].first.second; } else { pair<L, L> p; while (a != b) { if (a != 1) { p = ylos(a, 1, c); a = p.first; c = p.second; } if (b != 1) { p = ylos(b, 1, c2); b = p.first; c2 = p.second; } if (c == 1 || c2 == 1) break; } } if (c == 0 && c2 != 0) return c2; else if (c != 0 && c2 == 0) return c; else if (c < c2) return c; else if (c > c2) return c2; return c; }
Test details
Test 1
Group: 1, 2, 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 1 2 74 1 3 100 2 4 50 3 5 40 ... |
correct output |
---|
88687 |
user output |
---|
(empty) |
Test 2
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
5000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1103702320243776 |
user output |
---|
(empty) |
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) |