Submission #1613606
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int Nmax = (1<<17) + 5; ll st, dr, mid; int dad, cost, i, n, son[Nmax][2], edge[Nmax][2]; vector< pair<ll, ll> > solve(int node, ll val) { if(!son[node][0]) { vector< pair<ll, ll> > ans; ans.push_back({0, 0}); return ans; } auto a = solve(son[node][0], val), b = solve(son[node][1], val); vector< pair<ll, ll> > v1, v2; if(a.size() > b.size()) swap(a, b); val -= edge[node][0] + edge[node][1]; int i, j; j = 0; for(i = 0; i < a.size(); ++i) { while(j < b.size() && a[i].second + b[j].first <= val) ++j; if(j && !(v1.size() && v1.back().second == b[j-1].second + edge[node][1])) v1.push_back({ a[i].first + edge[node][0], b[j-1].second + edge[node][1] }); } j = 0; for(i = 0; i < a.size(); ++i) { while(j < b.size() && a[i].first + b[j].second > val) ++j; if(j < b.size()) { if(v2.size() && v2.back().first == b[j].first + edge[node][1]) v2.back().second = a[i].second + edge[node][0]; else v2.push_back({ b[j].first + edge[node][1], a[i].second + edge[node][0] }); } } vector< pair<ll, ll> > ans; i = 0; j = 0; while(i < v1.size() && j < v2.size()) { if(v1[i].first <= v2[j].first && v1[i].second <= v2[j].second) ++j; else if(v1[i].first >= v2[j].first && v1[i].second >= v2[j].second) ++i; else if(v1[i].first < v2[j].first) ans.push_back(v1[i++]); else ans.push_back(v2[j++]); } while(i < v1.size()) ans.push_back(v1[i++]); while(j < v2.size()) ans.push_back(v2[j++]); return ans; } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin >> n; for(i=2; i<=n; ++i) { cin >> dad >> cost; if(son[dad][0]) son[dad][1] = i, edge[dad][1] = cost; else son[dad][0] = i, edge[dad][0] = cost; } st = 0; dr = (ll)Nmax * Nmax; while(st <= dr) { mid = (st + dr) / 2; if(solve(1, mid).empty()) st = mid + 1; else dr = mid - 1; } cout << st << '\n'; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Shik and Travel |
User | Alexa2001 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2314 Byte |
Status | WA |
Exec Time | 566 ms |
Memory | 19712 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt, example2.txt, example3.txt |
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, example0.txt, example1.txt, example2.txt, example3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | WA | 10 ms | 256 KB |
001.txt | AC | 9 ms | 256 KB |
002.txt | WA | 10 ms | 256 KB |
003.txt | AC | 9 ms | 256 KB |
004.txt | AC | 10 ms | 256 KB |
005.txt | WA | 9 ms | 256 KB |
006.txt | AC | 9 ms | 256 KB |
007.txt | WA | 9 ms | 256 KB |
008.txt | WA | 9 ms | 256 KB |
009.txt | WA | 9 ms | 256 KB |
010.txt | WA | 546 ms | 2304 KB |
011.txt | WA | 547 ms | 2304 KB |
012.txt | WA | 546 ms | 2304 KB |
013.txt | WA | 544 ms | 2304 KB |
014.txt | AC | 551 ms | 2304 KB |
015.txt | WA | 546 ms | 2304 KB |
016.txt | WA | 547 ms | 2304 KB |
017.txt | AC | 546 ms | 2304 KB |
018.txt | WA | 545 ms | 2304 KB |
019.txt | WA | 541 ms | 2304 KB |
020.txt | WA | 553 ms | 2304 KB |
021.txt | WA | 544 ms | 2304 KB |
022.txt | WA | 546 ms | 2304 KB |
023.txt | WA | 559 ms | 2304 KB |
024.txt | WA | 566 ms | 2304 KB |
025.txt | WA | 545 ms | 2304 KB |
026.txt | AC | 503 ms | 2304 KB |
027.txt | WA | 547 ms | 2304 KB |
028.txt | AC | 501 ms | 2304 KB |
029.txt | AC | 501 ms | 2304 KB |
030.txt | AC | 536 ms | 1280 KB |
031.txt | AC | 540 ms | 2304 KB |
032.txt | AC | 540 ms | 2304 KB |
033.txt | AC | 547 ms | 1280 KB |
034.txt | AC | 531 ms | 1280 KB |
035.txt | AC | 541 ms | 2304 KB |
036.txt | AC | 537 ms | 1280 KB |
037.txt | WA | 527 ms | 1280 KB |
038.txt | AC | 548 ms | 1280 KB |
039.txt | AC | 447 ms | 2304 KB |
040.txt | AC | 454 ms | 5336 KB |
041.txt | AC | 468 ms | 6356 KB |
042.txt | AC | 470 ms | 6356 KB |
043.txt | AC | 468 ms | 6360 KB |
044.txt | AC | 354 ms | 19712 KB |
045.txt | AC | 504 ms | 11008 KB |
046.txt | AC | 523 ms | 13568 KB |
047.txt | AC | 522 ms | 11776 KB |
048.txt | AC | 519 ms | 16896 KB |
049.txt | AC | 1 ms | 256 KB |
example0.txt | AC | 1 ms | 256 KB |
example1.txt | AC | 1 ms | 256 KB |
example2.txt | AC | 1 ms | 256 KB |
example3.txt | AC | 1 ms | 256 KB |