Task: | Tietoverkko |
Sender: | Sahari Kempo |
Submission time: | 2021-10-17 15:24:22 +0300 |
Language: | C++17 |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.01 s | 1, 2, 3 | details |
#2 | WRONG ANSWER | 0.13 s | 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, ddef = 0, deri1 = 0, deri2 = 0, dylo = 0, dylo2 = 0, df = 0, detsi = 0; 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"; // cout << "ddef: " << ddef << " deri: " << deri1 << " deri2: " << deri2 << " dylo: " << dylo << " dylo2: " << dylo2 << " df: " << df << " detsi: " << detsi << "\n"; } void definef() { for (L i = 1; i <= n; i *= 2) { for (L j = 1 + i; j <= n; j++) { ddef++; //cout << "ddef++: " << ddef << "\n"; 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); deri1++; //cout << "deri1++: " << deri1 << "\n"; 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) { deri2++; //cout << "deri2++: " << deri2 << "\n"; kom = kom / 2; if (kom + sum <= k) { 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++) { dylo++; //cout << "dylo++: " << dylo << "\n"; 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++) { dylo2++; //cout << "dylo2++: " << dylo2 << "\n"; 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) { df++; //cout << "df++: " << df << "\n"; 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) { //cout << "a: " << a << " b: " << 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) { detsi++; //cout << "detsi++: " << detsi << "\n"; 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; } } //cout << " c: " << c << "\n"; 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: WRONG ANSWER
input |
---|
100 1 2 74 1 3 100 2 4 50 3 5 40 ... |
correct output |
---|
88687 |
user output |
---|
4468 |
Test 2
Group: 2, 3
Verdict: WRONG ANSWER
input |
---|
5000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1103702320243776 |
user output |
---|
1267338808706 |
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) |