oj.uz

Submission #1096533

# Submission time Handle Problem Language Result Execution time Memory
1096533 2024-10-04T17:19:46 Z AlgorithmWarrior Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 869 ms 81240 KB 
#include <bits/stdc++.h>
#define MAX 1000005

using namespace std;

vector<int>tree[MAX];
bool on_path[MAX];
int dp[MAX];
int h[MAX];
int tata[MAX];

int n,t,m;

void read(){
    cin>>n>>t>>m;
    int i;
    for(i=1;i<n;++i){
        int a,b;
        cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
}

void dfs(int nod){
    for(auto fiu : tree[nod])
    if(fiu!=tata[nod]){
        h[fiu]=h[nod]+1;
        tata[fiu]=nod;
        dfs(fiu);
    }
}

void dfs_dp(int nod,int tata){
    int first_val=0,second_val=0;
    for(auto fiu : tree[nod])
    if(fiu!=tata && !on_path[fiu]){
        dfs_dp(fiu,nod);
        ++dp[nod];
        if(dp[fiu]>first_val){
            second_val=first_val;
            first_val=dp[fiu];
        }
        else
            if(dp[fiu]>second_val)
                second_val=dp[fiu];
    }
    dp[nod]+=second_val;
}

void init_dfs_dp(){
    int nod1=m,nod2=t;
    on_path[m]=on_path[t]=1;
    while(nod1!=nod2){
        if(h[nod1]>h[nod2]){
            nod1=tata[nod1];
            on_path[nod1]=1;
        }
        else{
            nod2=tata[nod2];
            on_path[nod2]=1;
        }
    }
    int i;
    for(i=1;i<=n;++i)
        if(on_path[i])
            dfs_dp(i,0);
}

void write(){
    cout<<dp[m];
}

int main()
{
    read();
    dfs(1);
    init_dfs_dp();
    write();
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 80212 KB Output is correct
2 Correct 409 ms 74520 KB Output is correct
3 Correct 869 ms 81232 KB Output is correct
4 Correct 350 ms 52304 KB Output is correct
5 Correct 862 ms 81240 KB Output is correct
6 Correct 800 ms 81236 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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