Submission #1221905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221905		Nika533	Mousetrap (CEOI17_mousetrap)	C++20	45 / 100	4922 ms	60260 KiB

mousetrap

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=1e6+5;
int n,m,T,k,s,t,fix[N],dp[N];
vector<int> g[N];

void solve(int x, int p) {
	vector<int> v;
	for (auto y:g[x]) {
		if (y==p) continue;
		solve(y,x); v.pb(dp[y]);
	}
	int sz=v.size();
	sort(allr(v));
	if (sz==0) dp[x]=0;
	else if (sz==1) dp[x]=1;
	else dp[x]=sz+v[1];
}

vector<int> v;
bool found=0;
void dfs(int x, int p) {
	v.pb(x);
	if (x==t) {
		found=1; return;
	}
	for (auto y:g[x]) {
		if (y==p) continue;
		dfs(y,x);
		if (found==1) return;
	}
	v.pop_back();
}

void test_case() {
	scanf("%d%d%d",&n,&t,&s);
	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(s,s);
	for (auto x:v) fix[x]=1;
	int sz=v.size();
	
	int l=0,r=n,ans=0;
	while (l<=r) {
		int mid=(l+r)/2;
//		printf("MID %d\n",mid);
		int cnt=0;
		for (int i=0; i<sz-1; i++) {
			int x=v[i];
			for (auto y:g[x]) {
				if (fix[y]) continue;
				cnt++;
			}
		}
		int val=1;
		bool check=1;
		for (int i=0; i<sz-1; i++) {
			int x=v[i];
			vector<int> c;
			for (auto y:g[x]) {
				if (fix[y]) continue;
				solve(y,x); c.pb(dp[y]);
//				printf("Y %d %d\n",y,dp[y]);
			}
			sort(allr(c)); int sz1=c.size(); 
			for (int j=0; j<sz1; j++) {
				if (c[j]+cnt<=mid) {
					break;
				}
				val--;
			}
			if (cnt>mid) val-=1e9;
			if (val<0) {
				check=0; break;
			}
			val++;
			cnt-=sz1;
		}
//		printf("check %d\n",check);
		if (check) {
			ans=mid; r=mid-1;
		}
		else {
			l=mid+1;
		}
	}
	printf("%d\n",ans);
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1;
	while (T--) test_case();
}

Compilation message (stderr)

mousetrap.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
mousetrap.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main () {
      | ^~~~
mousetrap.cpp: In function 'void test_case()':
mousetrap.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d%d%d",&n,&t,&s);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
mousetrap.cpp:47:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |                 int a,b; scanf("%d%d",&a,&b);
      |                          ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35