oj.uz

Submission #1056096

# Submission time Handle Problem Language Result Execution time Memory
1056096 2024-08-13T07:44:54 Z 변재우(#11070) Summer Driving (CCO24_day1problem3) C++17
9 / 25
 741 ms 44880 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]=par2[0][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 F(int i, int j);
int G(int i);

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;
    // -> 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];
}
// 이건 좀 아닌 것 같음.

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 0 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 111 ms 33916 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9820 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 9 ms 11612 KB Output is correct
5 Correct 5 ms 2708 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 6 ms 11612 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 9308 KB Output is correct
11 Correct 7 ms 6536 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 0 ms 4444 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9820 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 9 ms 11612 KB Output is correct
5 Correct 5 ms 2708 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 6 ms 11612 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 9308 KB Output is correct
11 Correct 7 ms 6536 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 0 ms 4444 KB Output is correct
14 Correct 667 ms 38396 KB Output is correct
15 Correct 685 ms 32324 KB Output is correct
16 Correct 567 ms 37784 KB Output is correct
17 Correct 741 ms 33652 KB Output is correct
18 Correct 616 ms 31824 KB Output is correct
19 Correct 653 ms 44880 KB Output is correct
20 Correct 693 ms 44604 KB Output is correct
21 Correct 1 ms 4696 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 360 ms 34772 KB Output is correct
24 Correct 707 ms 44872 KB Output is correct
25 Correct 569 ms 29952 KB Output is correct
26 Correct 2 ms 4700 KB Output is correct
27 Correct 1 ms 4700 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 521 ms 34488 KB Output is correct
31 Correct 538 ms 34428 KB Output is correct
32 Correct 488 ms 34388 KB Output is correct
33 Correct 592 ms 43956 KB Output is correct

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 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 Correct 9 ms 9820 KB Output is correct
2 Correct 8 ms 8284 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 9 ms 11612 KB Output is correct
5 Correct 5 ms 2708 KB Output is correct
6 Correct 7 ms 8284 KB Output is correct
7 Correct 6 ms 11612 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 9308 KB Output is correct
11 Correct 7 ms 6536 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 0 ms 4444 KB Output is correct
14 Correct 667 ms 38396 KB Output is correct
15 Correct 685 ms 32324 KB Output is correct
16 Correct 567 ms 37784 KB Output is correct
17 Correct 741 ms 33652 KB Output is correct
18 Correct 616 ms 31824 KB Output is correct
19 Correct 653 ms 44880 KB Output is correct
20 Correct 693 ms 44604 KB Output is correct
21 Correct 1 ms 4696 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 360 ms 34772 KB Output is correct
24 Correct 707 ms 44872 KB Output is correct
25 Correct 569 ms 29952 KB Output is correct
26 Correct 2 ms 4700 KB Output is correct
27 Correct 1 ms 4700 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 521 ms 34488 KB Output is correct
31 Correct 538 ms 34428 KB Output is correct
32 Correct 488 ms 34388 KB Output is correct
33 Correct 592 ms 43956 KB Output is correct
34 Runtime error 26 ms 12868 KB Execution killed with signal 11
35 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 0 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 111 ms 33916 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -