Submission #1613564
Source Code Expand
#include <bits/stdc++.h> #define N 2000050 #define x first #define y second using namespace std; typedef long long LL; typedef pair<LL,LL> pii; pii f[N],tmp1[N],tmp2[N]; int ch[N][2],fa[N],v[N],tp[N],vis[N],le[N],ri[N],mid[N],n,m; LL lim; bool flag; void link(int a,int b) {ch[a][0] ? ch[a][1] = b : ch[a][0] = b;} inline int rd() {int r;scanf("%d",&r);return r;} void solve(int u,int l,int r) { if (!flag) return ; if (!ch[u][0] && !ch[u][1]) { f[l] = pii(v[u], v[u]); tp[u] = l; return ; } int L = ch[u][0], R = ch[u][1]; solve(L, l, mid[u]); solve(R, mid[u]+1, r); int T = tp[R], q1 = 0, q2 = 0; for (int i=tp[L];i>=l;i--) { while (T>=mid[u]+1 && f[i].y+f[T].x > lim) T--; if (T>=mid[u]+1 && f[i].y + f[T].x <= lim) tmp1[++q1] = pii(f[i].x, f[T].y); } T = tp[L]; for (int i=tp[R];i>=mid[u]+1;i--) { while (T>=l && f[i].y+f[T].x > lim) T--; if (T>=l && f[i].y+f[T].x <= lim) tmp2[++q2] = pii(f[i].x, f[T].y); } if (!q1 && !q2) {flag = 0; return ;} tp[u] = l-1; while (q1 || q2) { pii cur; if (q1 && q2) cur = tmp1[q1].x < tmp2[q2].x ? tmp1[q1--] : tmp2[q2--]; else cur = !q1 ? tmp2[q2--] : tmp1[q1--]; if (tp[u] >= l && cur.y >= f[ tp[u] ].y) continue; f[ ++tp[u] ] = cur; } for (int _=l;_<=tp[u];_++) f[_].x += v[u], f[_].y += v[u]; } void dfs(int u) { if (!ch[u][0] && !ch[u][1]) { le[u] = ri[u] = ++m; return ; } dfs(ch[u][0]); dfs(ch[u][1]); le[u] = le[ ch[u][0] ]; ri[u] = ri[ ch[u][1] ]; mid[u] = ri[ ch[u][0] ]; } bool go(LL x) { lim = x, flag = 1; solve(1,1,m); return flag; } int main() { n = rd(); for (int _=2;_<=n;_++) { fa[_] = rd(), v[_] = rd(); link(fa[_], _); if (!vis[ fa[_] ]) vis[ fa[_] ] = 1; } dfs(1); LL l = 1, r = 100000000000LL; while (l < r) { LL mi = (l + r) >> 1; if (go(mi)) r = mi; else l = mi + 1; } cout << l << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Shik and Travel |
User | HERESY |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1949 Byte |
Status | WA |
Exec Time | 129 ms |
Memory | 33536 KB |
Compile Error
./Main.cpp: In function ‘int rd()’: ./Main.cpp:16:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] inline int rd() {int r;scanf("%d",&r);return r;} ^
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 | 7 ms | 20736 KB |
001.txt | AC | 7 ms | 20736 KB |
002.txt | AC | 7 ms | 20736 KB |
003.txt | AC | 6 ms | 20736 KB |
004.txt | AC | 7 ms | 20736 KB |
005.txt | AC | 7 ms | 20736 KB |
006.txt | AC | 7 ms | 20736 KB |
007.txt | AC | 7 ms | 20736 KB |
008.txt | AC | 7 ms | 20736 KB |
009.txt | AC | 7 ms | 20736 KB |
010.txt | AC | 123 ms | 29440 KB |
011.txt | AC | 126 ms | 29440 KB |
012.txt | AC | 129 ms | 29440 KB |
013.txt | AC | 124 ms | 29440 KB |
014.txt | AC | 114 ms | 29440 KB |
015.txt | AC | 127 ms | 29440 KB |
016.txt | AC | 124 ms | 29440 KB |
017.txt | AC | 129 ms | 29440 KB |
018.txt | AC | 125 ms | 29440 KB |
019.txt | AC | 118 ms | 29440 KB |
020.txt | AC | 127 ms | 29440 KB |
021.txt | AC | 128 ms | 29440 KB |
022.txt | AC | 123 ms | 29440 KB |
023.txt | AC | 125 ms | 29440 KB |
024.txt | AC | 122 ms | 29440 KB |
025.txt | AC | 113 ms | 29440 KB |
026.txt | AC | 114 ms | 29440 KB |
027.txt | AC | 124 ms | 29440 KB |
028.txt | AC | 119 ms | 29440 KB |
029.txt | AC | 109 ms | 29440 KB |
030.txt | AC | 113 ms | 27136 KB |
031.txt | AC | 119 ms | 29440 KB |
032.txt | AC | 116 ms | 29440 KB |
033.txt | AC | 105 ms | 27136 KB |
034.txt | AC | 109 ms | 27136 KB |
035.txt | AC | 118 ms | 29440 KB |
036.txt | AC | 114 ms | 27136 KB |
037.txt | AC | 115 ms | 27136 KB |
038.txt | AC | 112 ms | 27136 KB |
039.txt | AC | 88 ms | 29440 KB |
040.txt | AC | 94 ms | 27136 KB |
041.txt | AC | 108 ms | 29440 KB |
042.txt | AC | 108 ms | 29440 KB |
043.txt | AC | 108 ms | 29440 KB |
044.txt | AC | 99 ms | 33536 KB |
045.txt | AC | 98 ms | 31488 KB |
046.txt | AC | 102 ms | 32128 KB |
047.txt | AC | 100 ms | 31616 KB |
048.txt | AC | 104 ms | 32896 KB |
049.txt | AC | 5 ms | 20736 KB |
example0.txt | AC | 5 ms | 20736 KB |
example1.txt | AC | 5 ms | 20736 KB |
example2.txt | AC | 5 ms | 20736 KB |
example3.txt | WA | 5 ms | 20864 KB |