oj.uz

답안 #85831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85831 2018-11-21T21:18:30 Z memetkagan44 Dynamite (POI11_dyn) C++11
100 / 100
 1551 ms 41440 KB 
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,cnt,ans,ar[300005],x,y;
    vector<int> v[300005];
    int solve(int yer,int dad,int say){
        int t=0,q=0;
        for(int i=0;i<v[yer].size();i++){
            int go=v[yer][i];
            if(dad==go)
                continue;
            int u=solve(go,yer,say);
            if(u==0)
                continue;
            if(u>0)
                q=max(q,u);
            else
                t=min(t,u);
        }
        if(abs(t)>=say){
            ans++;
            return say;
        }
        if(t==0 && q==0)
            return (-1)*ar[yer];
        if(q>abs(t))
            return q-1;
        return t-1;
    }
    int ctr(int k){
        ans=0;
        if(solve(1,0,k)<0)
            ans++;
        if(ans<=m)
            return 1;
        return 0;
    }
    int main(){
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&ar[i]);
            cnt+=ar[i];
        }
    	for(int i=1;i<n;i++){
            scanf("%d %d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        if(cnt<=m){
            printf("0\n");
            return 0;
        }
        int l=1,r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(ctr(mid))
                r=mid-1;
            else
                l=mid+1;
        }
        printf("%d\n",l);
        return 0;
    }

Compilation message

dyn.cpp: In function 'int solve(int, int, int)':
dyn.cpp:7:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[yer].size();i++){
                     ~^~~~~~~~~~~~~~
dyn.cpp: In function 'int main()':
dyn.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&n,&m);
         ~~~~~^~~~~~~~~~~~~~~
dyn.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&ar[i]);
             ~~~~~^~~~~~~~~~~~~
dyn.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&x,&y);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7496 KB Output is correct
4 Correct 8 ms 7576 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7600 KB Output is correct
2 Correct 8 ms 7604 KB Output is correct
3 Correct 8 ms 7608 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7656 KB Output is correct
2 Correct 10 ms 7684 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7692 KB Output is correct
2 Correct 9 ms 7700 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 8096 KB Output is correct
2 Correct 45 ms 8852 KB Output is correct
3 Correct 44 ms 9536 KB Output is correct
4 Correct 55 ms 11592 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 11592 KB Output is correct
2 Correct 95 ms 13192 KB Output is correct
3 Correct 170 ms 13460 KB Output is correct
4 Correct 147 ms 16484 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 16484 KB Output is correct
2 Correct 165 ms 16484 KB Output is correct
3 Correct 186 ms 16484 KB Output is correct
4 Correct 283 ms 19324 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 488 ms 19324 KB Output is correct
2 Correct 481 ms 19580 KB Output is correct
3 Correct 898 ms 27040 KB Output is correct
4 Correct 882 ms 27052 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1323 ms 27052 KB Output is correct
2 Correct 698 ms 27052 KB Output is correct
3 Correct 1551 ms 27052 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1204 ms 30348 KB Output is correct
2 Correct 1102 ms 30348 KB Output is correct
3 Correct 1383 ms 41440 KB Output is correct
4 Correct 332 ms 41440 KB Output is correct