oj.uz

Submission #1056102

# Submission time Handle Problem Language Result Execution time Memory
1056102 2024-08-13T07:46:20 Z 캐나다 선발고사 레전드(#11109) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 207 ms 28584 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++) {
        printf("%d\n",arr[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:79:13: warning: unused variable 'en' [-Wunused-variable]
   79 |         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 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct

Subtask #2
0.0 / 4.0

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

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 16728 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 2 ms 16728 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 57 ms 20208 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 2 ms 16728 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 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Incorrect 207 ms 28584 KB Output isn't correct
7 Halted 0 ms 0 KB -