oj.uz

Submission #1094888

# Submission time Handle Problem Language Result Execution time Memory
1094888 2024-09-30T18:16:23 Z Antares Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 740 ms 73300 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 23896 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 465 ms 72268 KB Output is correct
2 Correct 405 ms 67444 KB Output is correct
3 Correct 716 ms 73300 KB Output is correct
4 Correct 305 ms 48256 KB Output is correct
5 Correct 740 ms 73240 KB Output is correct
6 Correct 704 ms 73300 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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