Submission #1094888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094888		Antares	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	740 ms	73300 KiB

mousetrap

#include <iostream>
#include <vector>
using namespace std;
vector <int> v[1000001];
int dp[1000001];
int n,m,i,t,x,y;
void dfs (int nod,int t)
{
    int max1=0,max2=0;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (vecin==t)
            continue;
        dfs (vecin,nod);
        if (dp[vecin]>=max1)
        {
            max2=max1;
            max1=dp[vecin];
        }
        else if (dp[vecin]>max2)
            max2=dp[vecin];
    }
    dp[nod]=max2+v[nod].size ()-1;
}
int main ()
{
    /**
      t
      |
      m
   /  |  \
   v1 v2 v3
   dp[nod]=costul minim ca soricelul sa fie obligat sa ajunga in dp[t[nod]]
   dp[m]=max2 (dp[fiu])+nrfii-2 (fara m v2 si m v1)+1 (m v1)+1 (m v2)=max2 (dp[fiu])+nrfii
    **/
    cin>>n>>t>>m;
    for (i=1; i<n; i++)
    {
        cin>>x>>y;
        v[x].push_back (y);
        v[y].push_back (x);
    }
    dfs (m,t);
    cout<<dp[m];
    return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i=0; i<v[nod].size (); i++)
      |                   ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35