oj.uz

Submission #123072

# Submission time Handle Problem Language Result Execution time Memory
123072 2019-06-30T07:31:31 Z davitmarg Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 676 ms 109924 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>
#include <cassert>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,trap,m,u[1000006],nxt[1000006],dp[1000006],cnt[1000006],d[1000006],ans;
vector<int> g[1000006],t[1000006];

void maketree(int v)
{
    u[v]=1;
    if(v==trap)
	{
		nxt[v]=1;
        return;
	}
    for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
		if(u[to])
			continue;
        t[v].PB(to);
        maketree(to);
        if(nxt[to])
		{
			cnt[v]+=cnt[to];
			nxt[v]=1;
		}
	}
    cnt[v]+=t[v].size()-1;
    cnt[v]*=nxt[v];
}

void dfs(int v,int last=m,int sum=0)
{
    if(nxt[v])
	{
        last=v;
        sum=0;
	}
	else if(!t[v].empty())
		sum+=t[v].size()-1;

    vector<int> dps;
    for(int i=0;i<t[v].size();i++)
	{
		int to=t[v][i];
        d[to]=d[v]+1;
        dfs(to,last,sum);
        dps.PB(dp[to]);
	}
    if(t[v].empty())
        dp[v]=(cnt[last]+sum-1+d[v]-d[last])*(!nxt[v]);
    else
	{
        if(!nxt[v])
			dps.PB((cnt[last]+sum-1+d[v]-d[last])*(!nxt[v]));
        sort(all(dps));
        reverse(all(dps));
        if(dps.size()==1 || dps[0]==dps[1])
            dp[v]=dps[0];
        else
            dp[v]=dps[1]+1;
	}
}

int main()
{
    cin>>n>>trap>>m;
    for(int i=1;i<=n-1;i++)
	{
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].PB(b);
        g[b].PB(a);
	}
    maketree(m);
    d[1]=0;
	dfs(m);
    cout<<dp[m]<<endl;
	return 0;
}

/*

5 5 1
1 2
2 3
2 4
2 5

*/

Compilation message

mousetrap.cpp: In function 'void maketree(int)':
mousetrap.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs(int, int, int)':
mousetrap.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<t[v].size();i++)
                 ~^~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47352 KB Output is correct
2 Correct 52 ms 47324 KB Output is correct
3 Correct 52 ms 47356 KB Output is correct
4 Correct 52 ms 47308 KB Output is correct
5 Incorrect 52 ms 47352 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47352 KB Output is correct
2 Correct 52 ms 47324 KB Output is correct
3 Correct 52 ms 47356 KB Output is correct
4 Correct 52 ms 47308 KB Output is correct
5 Incorrect 52 ms 47352 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47352 KB Output is correct
2 Correct 52 ms 47324 KB Output is correct
3 Correct 52 ms 47356 KB Output is correct
4 Correct 52 ms 47308 KB Output is correct
5 Incorrect 52 ms 47352 KB Output isn't correct
6 Halted 0 ms 0 KB -