Submission #1692077
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
const int MAXN = 200000 + 100;
const long long INF = 0x1f1f1f1f1f1f1f1fll;
typedef pair<long long, long long> pii;
typedef vector<pii> vpii;
int n;
vector<int> son[MAXN], wei[MAXN];
vector<pii> list[MAXN];
long long f[MAXN];
void merge(const vpii &a, const vpii &b, vpii &c)
{
// int l = 0, r = 0;
// while(l < a.size() && r < b.size())
// if(a[l] < b[r])
// c.push_back(a[l]), l++;
// else
// c.push_back(b[r]), r++;
// while(l < a.size())
// c.push_back(a[l]), l++;
// while(r < b.size())
// c.push_back(b[r]), r++;
int l = a.size() - 1, r = b.size() - 1;
while(~l && ~r)
if(a[l] < b[r])
c.push_back(a[l]), l--;
else
c.push_back(b[r]), r--;
while(~l)
c.push_back(a[l]), l--;
while(~r)
c.push_back(b[r]), r--;
}
void arange(vpii &a)
{
if(!a.size()) return ;
int p = 0;
a[p] = a[0], p++;
for(int i = 1; i < a.size(); i++)
if(!(a[i - 1].first <= a[i].first && a[i - 1].second <= a[i].second))
a[p] = a[i], p++;
a.resize(p);
}
void print(vpii &a)
{
for(int i = 0; i < a.size(); i++)
cout << a[i].first << ' ' << a[i].second << " / ";
cout << endl;
}
bool dfs(int x, int fa, long long k)
{
// cout << k << " : " << x << endl;
if(son[x].size() == 0)
{
list[x].push_back(make_pair(0, 0));
return true;
}
int s0 = son[x][0], s1 = son[x][1], w0 = wei[x][0], w1 = wei[x][1];
if(!dfs(s0, x, k) || !dfs(s1, x, k)) return false;
// for(int i = 0; i < 2; i++)
// for(int j = 0; j < list[son[x][i]].size(); j++)
// list[son[x][i]][j] = make_pair(list[son[x][i]][j].first + wei[x][i], list[son[x][i]][j].second + wei[x][i]);
if(list[s0].size() > list[s1].size()) swap(s0, s1), swap(w0, w1);
static vector<pii> arr0, arr1;
arr0.clear(), arr1.clear();
int r = list[s1].size() - 1, l = 0;
for(int i = list[s0].size() - 1; i >= 0; i--)
{
while(r >= 0 && list[s0][i].second + list[s1][r].first + w0 + w1 > k) r--;
while(l < list[s1].size() && list[s0][i].second + list[s1][l].second + w0 + w1 > k) l++;
if(r >= 0 && l < list[s1].size())
arr0.push_back(make_pair(list[s0][i].first + w0, min(list[s1][r].second, list[s1][l].first) + w1));
else if(r >= 0)
arr0.push_back(make_pair(list[s0][i].first + w0, list[s1][r].second + w1));
else if(l < list[s1].size())
arr0.push_back(make_pair(list[s0][i].first + w0, list[s1][l].first + w1));
}
r = list[s1].size() - 1, l = 0;
for(int i = 0; i < list[s0].size(); i++)
{
while(r >= 0 && list[s0][i].first + list[s1][r].first + w0 + w1 > k) r--;
while(l < list[s1].size() && list[s0][i].first + list[s1][l].second + w0 + w1 > k) l++;
if(r >= 0 && l < list[s1].size())
arr1.push_back(make_pair(list[s0][i].second + w0, min(list[s1][r].second, list[s1][l].first) + w1));
else if(r >= 0)
arr1.push_back(make_pair(list[s0][i].second + w0, list[s1][r].second + w1));
else if(l < list[s1].size())
arr1.push_back(make_pair(list[s0][i].second + w0, list[s1][l].first + w1));
}
// cout << x << ' ' << arr0.size() << ' ' << arr1.size() << endl;
// for(int i = 0; i < arr0.size(); i++)
// cout << arr0[i].first << ' ' << arr0[i].second << endl;
// for(int i = 0; i < arr1.size(); i++)
// cout << arr1[i].first << ' ' << arr1[i].second << endl;
if(arr0.size() + arr1.size() == 0)
return false;
// reverse(arr0.begin(), arr0.end());
// reverse(arr1.begin(), arr1.end());
// cout << x << endl, print(arr0), , print(arr0);
// cout << endl;
// arange(arr0);
// arange(arr1);
merge(arr0, arr1, list[x]);
// arange(list[x]);
// cout << x << " : ", print(list[x]);
return true;
}
bool calc(long long k)
{
for(int i = 1; i <= n; i++)
list[i].clear();
return dfs(1, 0, k);
}
void solve()
{
long long l = 0, r = 40000000000ll, ans = 0;
while(l < r)
{
long long mid = (l + r) / 2;
if(calc(mid))
r = mid, ans = mid;
else
l = mid + 1;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
// freopen("travel.in", "r", stdin);
// freopen("travel.out", "w", stdout);
cin >> n;
for(int i = 2; i <= n; i++)
{
int x, z;
cin >> x >> z;
son[x].push_back(i), wei[x].push_back(z);
}
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Shik and Travel |
User |
ct123098 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4443 Byte |
Status |
WA |
Exec Time |
775 ms |
Memory |
39464 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 |
AC |
9 ms |
14464 KB |
001.txt |
AC |
9 ms |
14464 KB |
002.txt |
AC |
9 ms |
14464 KB |
003.txt |
AC |
9 ms |
14464 KB |
004.txt |
AC |
9 ms |
14464 KB |
005.txt |
AC |
9 ms |
14464 KB |
006.txt |
AC |
9 ms |
14464 KB |
007.txt |
AC |
9 ms |
14464 KB |
008.txt |
WA |
9 ms |
14464 KB |
009.txt |
AC |
9 ms |
14464 KB |
010.txt |
AC |
262 ms |
24704 KB |
011.txt |
WA |
243 ms |
24704 KB |
012.txt |
AC |
257 ms |
24704 KB |
013.txt |
WA |
264 ms |
24704 KB |
014.txt |
AC |
248 ms |
24704 KB |
015.txt |
AC |
290 ms |
24704 KB |
016.txt |
AC |
270 ms |
24704 KB |
017.txt |
AC |
300 ms |
24704 KB |
018.txt |
AC |
268 ms |
24704 KB |
019.txt |
AC |
253 ms |
24704 KB |
020.txt |
WA |
261 ms |
24704 KB |
021.txt |
AC |
255 ms |
24704 KB |
022.txt |
AC |
253 ms |
24704 KB |
023.txt |
WA |
256 ms |
24832 KB |
024.txt |
WA |
250 ms |
24704 KB |
025.txt |
AC |
219 ms |
24704 KB |
026.txt |
AC |
236 ms |
24704 KB |
027.txt |
AC |
246 ms |
24704 KB |
028.txt |
AC |
256 ms |
24704 KB |
029.txt |
AC |
234 ms |
24704 KB |
030.txt |
AC |
592 ms |
39464 KB |
031.txt |
AC |
757 ms |
39464 KB |
032.txt |
AC |
775 ms |
39464 KB |
033.txt |
AC |
553 ms |
39464 KB |
034.txt |
WA |
598 ms |
39464 KB |
035.txt |
AC |
744 ms |
39464 KB |
036.txt |
AC |
572 ms |
39464 KB |
037.txt |
AC |
622 ms |
39464 KB |
038.txt |
AC |
577 ms |
39464 KB |
039.txt |
AC |
724 ms |
39464 KB |
040.txt |
AC |
420 ms |
39464 KB |
041.txt |
AC |
565 ms |
39464 KB |
042.txt |
AC |
564 ms |
39464 KB |
043.txt |
AC |
559 ms |
39464 KB |
044.txt |
AC |
195 ms |
32768 KB |
045.txt |
AC |
200 ms |
28160 KB |
046.txt |
AC |
209 ms |
29568 KB |
047.txt |
AC |
210 ms |
28544 KB |
048.txt |
AC |
210 ms |
31360 KB |
049.txt |
AC |
6 ms |
14336 KB |
example0.txt |
AC |
6 ms |
14336 KB |
example1.txt |
AC |
5 ms |
14336 KB |
example2.txt |
AC |
6 ms |
14336 KB |
example3.txt |
AC |
6 ms |
14336 KB |