oj.uz

Submission #1056018

# Submission time Handle Problem Language Result Execution time Memory
1056018 2024-08-13T07:12:42 Z 변재우(#11070) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 100 ms 33992 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=3010;
int N, R, A, B, dep[Nmax], par[Nmax], p, l[Nmax], r[Nmax], par2[12][Nmax];
int Da[Nmax][Nmax], Db[Nmax];
bool chka[Nmax][Nmax], chkb[Nmax];
vector<int> adj[Nmax];

void DFS(int curr, int prev) {
    l[curr]=++p;
    for(int next:adj[curr]) if(next!=prev) dep[next]=dep[curr]+1, par[next]=curr, DFS(next, curr);
    r[curr]=p;
}

int LCA(int u, int v) {
    if(dep[u]<dep[v]) swap(u, v);
    for(int i=11; i>=0; i--) if(dep[par2[i][u]]>dep[v]) u=par2[i][u];
    if(dep[u]!=dep[v]) u=par2[0][u];
    for(int i=11; i>=0; i--) if(par2[i][u]!=par2[i][v]) u=par2[i][u], v=par2[i][v];
    if(u!=v) u=par2[0][u];
    return u;
}
int Dist(int u, int v) {
    return dep[u]+dep[v]-2*dep[LCA(u, v)];
}

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

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);
    }
    DFS(R, 0);
    for(int i=1; i<12; i++) for(int j=1; j<=N; j++) par2[i][j]=par2[i-1][par2[i-1][j]];
    cout<<F(R, 0);
    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;
    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);
    }
    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;
    for(int j=1; j<=N; j++) if(Dist(i, j)<=B && !chk[j]) 
        Db[i]=min(Db[i], F(j, 0));
    return Db[i];
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 4.0

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

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4700 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 7 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 12880 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 Incorrect 7 ms 4700 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 100 ms 33992 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -