Submission #1096533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096533		AlgorithmWarrior	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	869 ms	81240 KiB

mousetrap

#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
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35