oj.uz

Submission #1056178

# Submission time Handle Problem Language Result Execution time Memory
1056178 2024-08-13T08:05:58 Z 변재우(#11070) Summer Driving (CCO24_day1problem3) C++17
5 / 25
 239 ms 79040 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=300010, S=(1<<19), INF=1e18;
int N, R, A, B, X[Nmax];
int Da[Nmax], Da2[Nmax], Db[Nmax];
vector<int> adj[Nmax];

/*int F(int i, int j);
int G(int i);*/

class Seg {
public:
    Seg() {fill(Tree+1, Tree+2*S, INF);}
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    int Query(int l, int r) {return Query(1, 1, S, l, r);}
private:
    int Tree[2*S];
    void Update(int node, int s, int e, int k, int v) {
        if(s==e) {
            Tree[node]=v; return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
        Tree[node]=min(Tree[lch], Tree[rch]);
    }
    int Query(int node, int s, int e, int l, int r) {
        if(s>r || l>e) return INF;
        if(l<=s && e<=r) return Tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        return min(Query(lch, s, m, l, r), Query(rch, m+1, e, l, r));
    }
}T, Da_T, Da2_T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>R>>A>>B;
    if(A<=B) {
        cout<<1; return 0;
    }
    for(int i=1; i<N; i++) {
        int u, v; cin>>u>>v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    X[1]=R;
    for(int i=1; i<N; i++) X[i+1]=((adj[X[i]][0]==X[i-1])?adj[X[i]][1]:adj[X[i]][0]);
    for(int i=1; i<=N; i++) T.Update(i, X[i]);
    for(int i=N; i>=1; i--) {
        if(i+A<=N) Da[i]=Db[i+A];
        else Da[i]=T.Query(i, i+B);
        Da2[i]=X[i]; // minQuery
        Da_T.Update(i, Da[i]), Da2_T.Update(i, Da2[i]);
        if(i+B>N) continue;
        int j=i+B;
        Db[j]=min(Da2_T.Query(j-B, j-1), Da_T.Query(j, j+B));
    }
    cout<<Da[1];
    return 0;
}

/*int F(int i, int j) {
    if(chka[i][j]) return Da[i][j];
    chka[i][j]=true;
    bool flag=true;
    for(int k=1; k<=N; k++) if(dep[k]==dep[i]+A && l[i]<=l[k] && l[k]<=r[i] && !(l[j]<=l[k] && l[k]<=r[j]))
        Da[i][j]=max(Da[i][j], G(k)), flag=false;
    // -> i의 자식 중 i까지의 거리가 A인 점들에 대한 쿼리 -> BFS Ordering으로 처리 가능
    if(flag) {
        Da[i][j]=Nmax;
        for(int k=1; k<=N; k++) if(dep[k]<=dep[i]+B && l[i]<=l[k] && l[k]<=r[i] && !(l[j]<=l[k] && l[k]<=r[j]))
            Da[i][j]=min(Da[i][j], k);
        // -> i의 자식 중 i까지의 거리가 B 이하인 점들의 최솟값 -> 그냥 처리 가능
    }
    return Da[i][j];
}

int G(int i) {
    if(chkb[i]) return Db[i];
    chkb[i]=true;
    bool chk[Nmax]={0};
    Db[i]=Nmax;
    for(int j=i; dep[i]-dep[j]<B; j=par[j]) Db[i]=min(Db[i], F(par[j], j)), chk[par[j]]=true;
    // i부터 i로부터 B만큼 높은 부모까지의 쿼리 -> HLD로 처리 가능
    for(int j=1; j<=N; j++) if(Dist(i, j)<=B && !chk[j]) 
        Db[i]=min(Db[i], F(j, 0));
    // i부터 i까지의 거리가 B 이하인 점들에 대한 쿼리
    // 원 쿼리는 Centroid Decomposition + BFS Ordering으로 처리 가능
    return Db[i];
}
// 이건 좀 아닌 것 같음.
// 최종 시간 복잡도 O(Nlog^2N)에 해결이 가능은 함*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33368 KB Output is correct
2 Correct 4 ms 33372 KB Output is correct
3 Correct 4 ms 33248 KB Output is correct
4 Correct 4 ms 33368 KB Output is correct
5 Correct 4 ms 33372 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 50768 KB Output is correct
2 Correct 175 ms 54864 KB Output is correct
3 Correct 171 ms 54632 KB Output is correct
4 Correct 209 ms 54608 KB Output is correct
5 Correct 188 ms 54100 KB Output is correct
6 Correct 239 ms 54612 KB Output is correct
7 Correct 236 ms 54608 KB Output is correct
8 Correct 201 ms 54636 KB Output is correct
9 Correct 4 ms 33368 KB Output is correct
10 Correct 171 ms 54740 KB Output is correct
11 Correct 204 ms 54672 KB Output is correct
12 Correct 4 ms 33372 KB Output is correct

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 71624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 71624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 79040 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 71624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33368 KB Output is correct
2 Correct 4 ms 33372 KB Output is correct
3 Correct 4 ms 33248 KB Output is correct
4 Correct 4 ms 33368 KB Output is correct
5 Correct 4 ms 33372 KB Output is correct
6 Correct 203 ms 50768 KB Output is correct
7 Correct 175 ms 54864 KB Output is correct
8 Correct 171 ms 54632 KB Output is correct
9 Correct 209 ms 54608 KB Output is correct
10 Correct 188 ms 54100 KB Output is correct
11 Correct 239 ms 54612 KB Output is correct
12 Correct 236 ms 54608 KB Output is correct
13 Correct 201 ms 54636 KB Output is correct
14 Correct 4 ms 33368 KB Output is correct
15 Correct 171 ms 54740 KB Output is correct
16 Correct 204 ms 54672 KB Output is correct
17 Correct 4 ms 33372 KB Output is correct
18 Runtime error 25 ms 71624 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -