oj.uz

Submission #108858

# Submission time Handle Problem Language Result Execution time Memory
108858 2019-05-02T10:18:16 Z fjzzq2002 Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 1501 ms 67692 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<ll> ss;
	for esb(x,e,b)
		if(b!=fa[x])
		{
			if(!sp[b])
				ss.pb(f[b]+1+so[x].size()-1-sp[x]); //???
			else
				ss.pb(f[b]);
		}
	sort(ss.begin(),ss.end(),greater<ll>());
	if(ss.size()==0) f[x]=0;
	else if(ss.size()==1) f[x]=!sp[x];
	else f[x]=ss[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 24 ms 23808 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Incorrect 24 ms 23808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 66904 KB Output is correct
2 Correct 505 ms 62636 KB Output is correct
3 Correct 1501 ms 67576 KB Output is correct
4 Correct 618 ms 45944 KB Output is correct
5 Correct 1456 ms 67608 KB Output is correct
6 Correct 1485 ms 67692 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Incorrect 24 ms 23808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 23 ms 24056 KB Output is correct
4 Incorrect 24 ms 23808 KB Output isn't correct
5 Halted 0 ms 0 KB -