oj.uz

Submission #1055943

# Submission time Handle Problem Language Result Execution time Memory
1055943 2024-08-13T06:44:53 Z 캐나다 선발고사 레전드(#11109) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 2 ms 1628 KB 
#include <bits/stdc++.h>
using namespace std;

int n,r,a,b;
const int MAX=3005;
int ind[MAX];
int sz[MAX];
int md[MAX];
vector<int> adj[MAX];
int dep[MAX];
int f=0;
int p[MAX];
int par[MAX][MAX];

void dfs(int v,int pr) {
    p[v]=pr;
    md[v]=dep[v];
    sz[v]=1;
    ind[v]=f++;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt!=pr) {
            dep[nt]=dep[v]+1;
            dfs(nt,v);
            md[v]=max(md[v],md[nt]);
            sz[v]+=sz[nt];
        }
    }
}

int dp[MAX][2][2];
int dist[MAX];
queue<int> q;

int ans(int v,int t1,int t) { //t1=1�̸� v�� �θ𿡼� v �������δ� �� ���� ���� t=0�� alice, t=1�� bob
    if (dp[v][t1][t]!=-1) {
        return dp[v][t1][t];
    }
    if (t==0) {
        int now=(t1?p[v]:v);
        int ret=0;
        for(int i=1;i<=n;i++) {
            if (ind[now]<=ind[i]&&ind[i]<=ind[now]+sz[now]-1) {
                if (t1&&ind[v]<=ind[i]&&ind[i]<=ind[v]+sz[v]-1) {
                    continue;
                }
                if (dep[i]==dep[now]+a) {
                    ret=max(ret,ans(i,0,1));
                }
            }
        }
        if (ret==0) {
            for(int i=1;i<=n;i++) {
                dist[i]=-1;
            }
            while (!q.empty()) {
                q.pop();
            }
            q.push(now);
            dist[now]=0;
            while (!q.empty()) {
                int vv=q.front();
                q.pop();
                for(int i=0;i<adj[vv].size();i++) {
                    int nt=adj[vv][i];
                    if (dist[nt]==-1) {
                        dist[nt]=dist[vv]+1;
                        q.push(nt);
                    }
                }
            }
            ret=n;
            for(int i=1;i<=n;i++) {
                if (dist[i]!=-1&&dist[i]<=b) {
                    ret=min(ret,i);
                }
            }
        }
        //printf("%d %d %d %d\n",v,t1,t,ret);
        return dp[v][t1][t]=ret;
    }
    for(int i=1;i<=n;i++) {
        dist[i]=-1;
    }
    while (!q.empty()) {
        q.pop();
    }
    q.push(v);
    dist[v]=0;
    while (!q.empty()) {
        int vv=q.front();
        q.pop();
        for(int i=0;i<adj[vv].size();i++) {
            int nt=adj[vv][i];
            if (dist[nt]==-1) {
                dist[nt]=dist[vv]+1;
                q.push(nt);
            }
        }
    }
    vector<int> vec;
    for(int i=1;i<=n;i++) {
        if (dist[i]!=-1&&dist[i]<=b) {
            vec.push_back(i);
        }
    }
    int ret=n;
    for(int i:vec) {
        if (i!=v&&ind[i]<=ind[v]&&ind[v]<=ind[i]+sz[i]-1) {
            int diff=dep[v]-dep[i];
            ret=min(ret,ans(par[v][diff-1],1,0));
        }
        else {
            ret=min(ret,ans(i,0,0));
        }
    }
    //printf("%d %d %d %d\n",v,t1,t,ret);
    return dp[v][t1][t]=ret;
}

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);
    }
    dfs(r,-1);
    for(int i=1;i<=n;i++) {
        int now=i;
        int cnt=0;
        while (now!=-1) {
            par[now][cnt]=now;
            cnt++;
            now=p[now];
        }
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",ans(r,0,0));
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Main.cpp: In function 'int ans(int, int, int)':
Main.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                 for(int i=0;i<adj[vv].size();i++) {
      |                             ~^~~~~~~~~~~~~~~
Main.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int i=0;i<adj[vv].size();i++) {
      |                     ~^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%d %d %d %d",&n,&r,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 604 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 2 ms 1628 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 1628 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 1 ms 604 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 2 ms 1628 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 344 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 1 ms 604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -