Submission #1839736


Source Code Expand

#include<bits/stdc++.h>
#define N ((1<<17)+3)
#define LL long long
using namespace std;
vector<int> son[N];
vector<pair<LL,LL> > dp[N];
LL mid,dis[N];
vector<pair<LL,LL> > temp;
bool DFS(int u,int fr){
    dp[u].clear();
    for(int i:son[u]) 
        if(!DFS(i,u))
            return false;
    if(son[u].size()==0){
        dp[u].push_back(make_pair(0,0));
    }else{
        temp.clear();
        int l=son[u][0],r=son[u][1];LL limit=mid-dis[l]-dis[r];
        if(dp[l].size()>dp[r].size()) swap(l,r);
        for(int i=0,p=0;i<dp[l].size()&&p<dp[r].size();i++){
            while(p+1<dp[r].size() && dp[l][i].second+dp[r][p+1].first <= limit) p++;
            if(dp[l][i].second+dp[r][p].first <= limit) 
                temp.push_back(make_pair( dp[l][i].first+dis[l],dp[r][p].second+dis[r] ));
        }
        for(int i=temp.size()-1;i>=0;i--) 
            temp.push_back(make_pair(temp[i].second,temp[i].first));
        sort(temp.begin(),temp.end());
        for(pair<LL,LL> x:temp){
            if(dp[u].size()==0|| x.second < dp[u][dp[u].size()-1].second )
                dp[u].push_back(x);
        }
    }
    return dp[u].size()!=0;
}

int n,fa[N];

int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d%lld",&fa[i],&dis[i]),son[fa[i]].push_back(i);
    LL l=-1,r=1e12;//(]
    while(l+1<r){
        mid=(l+r)>>1;
        if(!DFS(1,0)) l=mid;
        else r=mid;
    }
    cout<<r<<endl;
    return 0;
}

Submission Info

Submission Time
Task E - Shik and Travel
User Wuvin
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 1481 Byte
Status AC
Exec Time 531 ms
Memory 33652 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:39:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:40:81: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for(int i=2;i<=n;i++) scanf("%d%lld",&fa[i],&dis[i]),son[fa[i]].push_back(i);
                                                                                 ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 4
AC × 54
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 6 ms 6528 KB
001.txt AC 7 ms 6528 KB
002.txt AC 7 ms 6528 KB
003.txt AC 6 ms 6528 KB
004.txt AC 7 ms 6528 KB
005.txt AC 7 ms 6528 KB
006.txt AC 6 ms 6528 KB
007.txt AC 7 ms 6528 KB
008.txt AC 7 ms 6528 KB
009.txt AC 6 ms 6528 KB
010.txt AC 256 ms 15104 KB
011.txt AC 292 ms 15104 KB
012.txt AC 247 ms 15104 KB
013.txt AC 268 ms 15104 KB
014.txt AC 251 ms 15104 KB
015.txt AC 258 ms 15104 KB
016.txt AC 281 ms 15104 KB
017.txt AC 262 ms 15104 KB
018.txt AC 262 ms 15104 KB
019.txt AC 249 ms 14976 KB
020.txt AC 281 ms 15104 KB
021.txt AC 272 ms 15104 KB
022.txt AC 258 ms 15104 KB
023.txt AC 275 ms 15104 KB
024.txt AC 271 ms 15104 KB
025.txt AC 239 ms 15104 KB
026.txt AC 238 ms 14592 KB
027.txt AC 255 ms 15104 KB
028.txt AC 238 ms 14592 KB
029.txt AC 231 ms 14592 KB
030.txt AC 208 ms 15104 KB
031.txt AC 328 ms 15104 KB
032.txt AC 260 ms 15104 KB
033.txt AC 195 ms 15104 KB
034.txt AC 212 ms 15104 KB
035.txt AC 272 ms 15104 KB
036.txt AC 218 ms 15104 KB
037.txt AC 207 ms 14976 KB
038.txt AC 216 ms 15104 KB
039.txt AC 201 ms 14080 KB
040.txt AC 449 ms 33652 KB
041.txt AC 511 ms 33396 KB
042.txt AC 517 ms 33396 KB
043.txt AC 531 ms 33396 KB
044.txt AC 187 ms 24320 KB
045.txt AC 201 ms 19712 KB
046.txt AC 208 ms 20992 KB
047.txt AC 204 ms 20096 KB
048.txt AC 208 ms 22784 KB
049.txt AC 3 ms 6400 KB
example0.txt AC 3 ms 6400 KB
example1.txt AC 3 ms 6400 KB
example2.txt AC 3 ms 6400 KB
example3.txt AC 3 ms 6400 KB