Submission #1690835
Source Code Expand
#include <cstdio>
typedef long long LL;
const int N=131100;
int l[N],r[N],lef[N],rig[N],v[N],cnt,tot;
LL Mid;
struct P{
LL x,y;
P(const LL xx=0,const LL yy=0):x(xx),y(yy){}
}a[N],b[N];
void solve(int l1,int r1,int l2,int r2,LL val,int v1,int v2){
for (int i=l1,j=l2;i<=r1;i++){
for (;j<=r2 && a[i].y+a[j].x<=val;j++);
if (j>l2) b[++tot]=P(a[i].x+v1,a[j-1].y+v2);
}
}
int merge(int mid,int r,int l){
int t=l-1;
for (int i=1,j=mid+1;i<=mid || j<=r;){
P po;
if (i<=mid && (j>r || b[i].x<b[j].x)) po=b[i++];
else po=b[j++];
if (t<l) a[++t]=po;
else if (a[t].x<po.x && a[t].y>po.y) a[++t]=po;
else if (a[t].x==po.x && a[t].y>po.y) a[t].y=po.y;
}
return t;
}
bool dfs(int x){
int s1=l[x],s2=r[x];
if (!s1){
lef[x]=rig[x]=++cnt;
a[cnt].x=a[cnt].y=0;
return 1;
}
if (!dfs(s1) || !dfs(s2)) return 0;
LL val=Mid-v[s1]-v[s2];
tot=0;lef[x]=lef[s1];
solve(lef[s1],rig[s1],lef[s2],rig[s2],val,v[s1],v[s2]);
int m=tot;
solve(lef[s2],rig[s2],lef[s1],rig[s1],val,v[s2],v[s1]);
rig[x]=merge(m,tot,lef[x]);
return lef[x]<=rig[x];
}
int main(){
int n;
scanf("%d\n",&n);
LL L=0,R=0,ans=0;
for (int i=2;i<=n;i++){
int fa;
scanf("%d%d",&fa,&v[i]);
if (!l[fa]) l[fa]=i;
else r[fa]=i;
R+=v[i];
}
for (;L<=R;){
Mid=(L+R)>>1;
cnt=0;
if (dfs(1)) ans=Mid,R=Mid-1;
else L=Mid+1;
}
printf("%lld\n",ans);
}
Submission Info
Submission Time
2017-10-17 21:31:06+0900
Task
E - Shik and Travel
User
aufeas
Language
C++14 (GCC 5.4.1)
Score
1400
Code Size
1417 Byte
Status
AC
Exec Time
169 ms
Memory
9856 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:52:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d\n",&n);
^
./Main.cpp:56:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&fa,&v[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1400 / 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
4 ms
6272 KB
001.txt
AC
4 ms
6272 KB
002.txt
AC
4 ms
6272 KB
003.txt
AC
4 ms
6272 KB
004.txt
AC
4 ms
6272 KB
005.txt
AC
4 ms
6272 KB
006.txt
AC
4 ms
6272 KB
007.txt
AC
4 ms
6272 KB
008.txt
AC
4 ms
6272 KB
009.txt
AC
4 ms
6272 KB
010.txt
AC
103 ms
6784 KB
011.txt
AC
110 ms
6784 KB
012.txt
AC
112 ms
6784 KB
013.txt
AC
113 ms
6784 KB
014.txt
AC
106 ms
6784 KB
015.txt
AC
111 ms
6784 KB
016.txt
AC
113 ms
6784 KB
017.txt
AC
112 ms
6784 KB
018.txt
AC
115 ms
6784 KB
019.txt
AC
117 ms
6784 KB
020.txt
AC
119 ms
6784 KB
021.txt
AC
119 ms
6784 KB
022.txt
AC
119 ms
6784 KB
023.txt
AC
119 ms
6784 KB
024.txt
AC
115 ms
6912 KB
025.txt
AC
118 ms
6784 KB
026.txt
AC
107 ms
6784 KB
027.txt
AC
112 ms
6784 KB
028.txt
AC
110 ms
6784 KB
029.txt
AC
103 ms
6784 KB
030.txt
AC
105 ms
6528 KB
031.txt
AC
106 ms
6784 KB
032.txt
AC
108 ms
6784 KB
033.txt
AC
91 ms
6528 KB
034.txt
AC
105 ms
6528 KB
035.txt
AC
114 ms
6784 KB
036.txt
AC
114 ms
6528 KB
037.txt
AC
118 ms
6528 KB
038.txt
AC
110 ms
6528 KB
039.txt
AC
92 ms
6784 KB
040.txt
AC
154 ms
6528 KB
041.txt
AC
169 ms
6784 KB
042.txt
AC
169 ms
6784 KB
043.txt
AC
169 ms
6784 KB
044.txt
AC
110 ms
9856 KB
045.txt
AC
123 ms
8320 KB
046.txt
AC
122 ms
8832 KB
047.txt
AC
122 ms
8448 KB
048.txt
AC
123 ms
9344 KB
049.txt
AC
2 ms
6272 KB
example0.txt
AC
2 ms
6272 KB
example1.txt
AC
2 ms
6272 KB
example2.txt
AC
2 ms
6272 KB
example3.txt
AC
2 ms
6272 KB