QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#37350#791. MousetrapMonkeyKing0 148ms71028kbC++2.9kb2022-07-01 10:57:592022-07-01 10:58:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-01 10:58:01]
  • 评测
  • 测评结果:0
  • 用时:148ms
  • 内存:71028kb
  • [2022-07-01 10:57:59]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long 
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define mt make_tuple
#define ull unsigned long long 
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
const int inf=1039714778;
const int mod=1e9+7;
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
template <typename T> inline void chmin(T &x,const T &b) {x=min(x,b);}
template <typename T> inline void chmax(T &x,const T &b) {x=max(x,b);}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31) & mod;}

template <typename T>
ostream & operator << (ostream &cout,const vector<T> &v)
{
	cout<<'{';
	int fst=1;
	for(auto x:v)
	{
		if(fst) fst=0;
		else cout<<',';
		cout<<x;
	}
	cout<<'}';
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream &cout,const pair<T1,T2> &o)
{
	cout<<'('<<o.first<<','<<o.second<<')';
	return cout;
}

namespace FastIO
{
	int cursor=(1<<20);
	char buf[(1<<20)+5];
	char getchar()
	{
		if(cursor==(1<<20))
		{
			cursor=0;
			fread(buf,1,(1<<20),stdin);
		}
		return buf[cursor++];
	}
	int getnum()
	{
		char ch=0;
		int res=0;
		while(!isdigit(ch)) ch=getchar();
		while(isdigit(ch))
		{
			res=res*10+ch-'0';
			ch=getchar();
		}
		return res;
	}
}
using FastIO::getnum;

int n,rt,src;
vector<int> edges[1000005];
int nxt[1000005];
int par[1000005];

void go(int x,int par)
{
	::par[x]=par;
	for(auto u:edges[x])
	{
		if(u==par) continue;
		go(u,x);
	}
}

int dp[1000005];
void dfs(int x,int cost)
{
	for(auto u:edges[x])
	{
		if(u==par[x]) continue;
		dfs(u,cost+(int)edges[x].size()-1-(nxt[x]!=-1));
	}
	if(nxt[x]!=-1) return;
	vector<int> v;
	v.reserve(edges[x].size());
	for(auto u:edges[x])
	{
		if(u!=par[x]) v.emplace_back(dp[u]);
	}
	sort(all(v));
	reverse(all(v));
	if(!v.size())
	{
		dp[x]=cost;
	}
	else if(v.size()==1)
	{
		dp[x]=cost+1;
	}
	else
	{
		dp[x]=min(v[0],v[1]+1);
	}
}

int check(int k)
{
	int rm=0,used=0;
	for(int x=src;x!=rt;x=par[x])
	{
		rm++;
		int cnt=0;
		for(auto u:edges[x])
		{
			if(u==par[x] || u==nxt[x]) continue;
			if(dp[u]+used>k)
			{
				rm--;
				cnt++;
			}
		}
		if(rm<0) return false;
		used+=cnt;
	}
	return true;
}

int main()
{
	// freopen("input.txt","r",stdin);
	n=getnum();rt=getnum();src=getnum();
	rt--;src--;
	if(rt==src)
	{
		puts("0");
		return 0;
	}
	for(int i=0;i<n-1;i++)
	{
		int x=getnum(),y=getnum();
		x--;y--;
		edges[x].emplace_back(y);
		edges[y].emplace_back(x);
	}
	go(rt,-1);
	memset(nxt,-1,sizeof(nxt));
	int x=src;
	while(x!=rt)
	{
		nxt[par[x]]=x;
		x=par[x];
	}
	dfs(nxt[rt],0);
	// cout<<dp[9]<<endl;
	int l=1,r=n,mid,res;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid))
		{
			res=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<res<<endl;
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 30944kb

input:

10 2 10
2 1
3 2
4 2
5 3
6 3
7 4
8 4
9 5
10 5

output:

1

result:

wrong answer 1st lines differ - expected: '2', found: '1'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 148ms
memory: 71028kb

input:

1000000 1 2
2 1
3 2
4 2
5 3
6 3
7 4
8 4
9 5
10 5
11 6
12 6
13 7
14 7
15 8
16 8
17 9
18 9
19 10
20 10
21 11
22 11
23 12
24 12
25 13
26 13
27 14
28 14
29 15
30 15
31 16
32 16
33 17
34 17
35 18
36 18
37 19
38 19
39 20
40 20
41 21
42 21
43 22
44 22
45 23
46 23
47 24
48 24
49 25
50 25
51 26
52 26
53 27
5...

output:

38

result:

wrong answer 1st lines differ - expected: '36', found: '38'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%