oj.uz

Submission #1056107

# Submission time Handle Problem Language Result Execution time Memory
1056107 2024-08-13T07:48:00 Z 캐나다 선발고사 레전드(#11109) Summer Driving (CCO24_day1problem3) C++17
5 / 25
 390 ms 30548 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX=300005;
int dp0[MAX];
int dp1[MAX];
int save[MAX];
int n,r,a,b;
int arr[MAX];
vector<int> adj[MAX];
const int sz=524288;
int seg[sz*2];
int save1[MAX];

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return n;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return min(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,int val) {
    i+=sz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=min(seg[i*2],seg[i*2+1]);
    }
}

int main(void) {
    scanf("%d %d %d %d",&n,&r,&a,&b);
    if (a<=b) {
        printf("1");
        return 0;
    }
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int now=r;
    int pr=-1;
    arr[0]=r;
    for(int cnt=1;cnt<n;cnt++) {
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i];
            if (nt!=pr) {
                arr[cnt]=nt;
                pr=now;
                now=nt;
                break;
            }
        }
    }
    for(int i=0;i<n;i++) {
        update(i,arr[i]);
    }
    for(int i=0;i<n;i++) {
        int en=min(i+b-1,n-1);
        save[i]=sum(i,en);
        int st=max(0,i-b+1);
        save1[i]=sum(st,i);
    }
    for(int i=n-1;i>=0;i--) {
        if (i+a<n) {
            dp0[i]=dp1[i+a];
        }
        else {
            dp0[i]=min(save[i],i+b<n?arr[i+b]:n);
        }
        update(i,dp0[i]);
        int en=min(i+b,n-1);
        if (i!=0) {
            dp1[i]=min(save1[i-1],sum(i,min(i+b,n-1)));
        }
    }
    printf("%d",dp0[0]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
Main.cpp:78:13: warning: unused variable 'en' [-Wunused-variable]
   78 |         int en=min(i+b,n-1);
      |             ^~
Main.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d %d %d",&n,&r,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 4 ms 7504 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 25188 KB Output is correct
2 Correct 294 ms 24916 KB Output is correct
3 Correct 271 ms 26704 KB Output is correct
4 Correct 293 ms 24912 KB Output is correct
5 Correct 292 ms 28088 KB Output is correct
6 Correct 347 ms 28848 KB Output is correct
7 Correct 390 ms 28752 KB Output is correct
8 Correct 253 ms 30548 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 291 ms 30504 KB Output is correct
11 Correct 314 ms 29012 KB Output is correct
12 Correct 3 ms 7256 KB Output is correct

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 4 ms 7504 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 284 ms 25188 KB Output is correct
7 Correct 294 ms 24916 KB Output is correct
8 Correct 271 ms 26704 KB Output is correct
9 Correct 293 ms 24912 KB Output is correct
10 Correct 292 ms 28088 KB Output is correct
11 Correct 347 ms 28848 KB Output is correct
12 Correct 390 ms 28752 KB Output is correct
13 Correct 253 ms 30548 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 291 ms 30504 KB Output is correct
16 Correct 314 ms 29012 KB Output is correct
17 Correct 3 ms 7256 KB Output is correct
18 Incorrect 3 ms 7768 KB Output isn't correct
19 Halted 0 ms 0 KB -