oj.uz

Submission #108856

# Submission time Handle Problem Language Result Execution time Memory
108856 2019-05-02T10:12:25 Z fjzzq2002 Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 501 ms 67272 KB 
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 2000555
int n,t,m,fa[SZ],f[SZ]; Edg
vector<int> so[1000555];
void dfs(int x)
{
	for esb(x,e,b)
		if(b!=fa[x]) fa[b]=x,so[x].pb(b),dfs(b);
}
bool sp[SZ];
void dp(int x)
{
	if(x==m)
	{
		f[x]=0;
		return;
	}
	for esb(x,e,b)
		if(b!=fa[x]) dp(b);
	vector<int> ss;
	for esb(x,e,b)
		if(b!=fa[x])
		{
			if(!sp[b])
				ss.pb(f[b]+(int)so[x].size()-sp[x]); //???
			else
				ss.pb(f[b]);
		}
	sort(ss.begin(),ss.end(),greater<int>());
	if(ss.size()==0) f[x]=0;
	else if(ss.size()==1) f[x]=min(1,ss[0]);
	else f[x]=min(ss[0],ss[1]+1);
	if(sp[x]) f[x]-=so[x].size()-1;
//	cout<<x<<"w"<<f[x]<<"\n";
}
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<n;++i)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		adde(a,b);
	}
	dfs(t);
	ll ans=0;
	if(t==m)
	{
		puts("0");
		return 0;
	}
	for(int j=m;;j=fa[j])
	{
		sp[j]=1;
		if(j!=m)
			ans+=so[j].size()-1;
		if(j==t) break;
	}
	//cerr<<"CA:"<<ans<<"\n";
	dp(t); ans+=f[t];
	printf("%lld\n",ans);
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&t);
  ~~~~~^~~~~~~~~~~~~~~~~~~
mousetrap.cpp:73:8: 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 23 ms 23936 KB Output is correct
2 Correct 26 ms 23936 KB Output is correct
3 Correct 29 ms 23936 KB Output is correct
4 Correct 26 ms 23872 KB Output is correct
5 Incorrect 26 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23936 KB Output is correct
2 Correct 26 ms 23936 KB Output is correct
3 Correct 29 ms 23936 KB Output is correct
4 Correct 26 ms 23872 KB Output is correct
5 Incorrect 26 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23936 KB Output is correct
2 Correct 26 ms 23936 KB Output is correct
3 Correct 29 ms 23936 KB Output is correct
4 Correct 26 ms 23872 KB Output is correct
5 Incorrect 26 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -