Submission #122779

#	Time	Username	Problem	Language	Result	Execution time	Memory
122779		davitmarg	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	68 ms	17244 KiB

mousetrap

/*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,used[100005],p[100005],dp[100005],ans;
vector<int> g[100005],ord;

void dfs(int v)
{
	used[v]=1;
	if(v==trap)
	{
		p[v]=1;
		return;
	}
    vector<int> t;
    for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
        if(used[to])
			continue;
        dfs(to);
        if(!p[to])
			t.PB(to);
        else
			p[v]=1;
	}

    sort(all(t),[](int a,int b)
    {
    	return dp[a]>dp[b];
    });

    dp[v]+=t.size();
    for(int i=1;i<t.size();i+=2)
		dp[v]+=dp[t[i]];

    if(p[v])
        ord.PB(v);
}

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);
	}
    dfs(m);
    reverse(all(ord));
    ord.pop_back();
    for(int i=0;i<ord.size();i++)
        ans+=dp[ord[i]];
    cout<<ans<<endl;
	return 0;
}

/*




*/

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int)':
mousetrap.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
mousetrap.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<t.size();i+=2)
                 ~^~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ord.size();i++)
                 ~^~~~~~~~~~~
mousetrap.cpp:71: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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35