1 - 帖子 - Liuser's OJ

#pragma GCC optimize(2,3,"Ofast")
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int MAXN=1e3+5;
int n,m,sx,sy,ex,ey,flag[MAXN][MAXN],dir[4][2]={{1,-2},{-1,-2},{2,-1},{-2,-1}}; 
int dfs(int x,int y){
	if(!flag[x][y]){ 
		for(int i=0,nx,ny,t;i<4;i++){
			nx=x+dir[i][0],ny=y+dir[i][1];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
				t=dfs(nx,ny);
				if(t!=-1145141919810)	flag[x][y]+=t; 
			}
			if(flag[x][y]==0)	flag[x][y]=-1145141919810;
		} 
	}
	return flag[x][y];
}
signed main(){
	cin>>n>>m>>sx>>sy>>ex>>ey;
	flag[sx][sy]=1;
	dfs(sx,sy);
	cout<<flag[ex][ey];
	return 0;
}

DKX

2023-08-10 18:33:01


#pragma GCC optimize(2,3,"Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<vector>
#include<climits>
#define int long long
#define pb push_back
using namespace std;
const int MAXN=1e5+5;
int n,tot,ans=INT_MAX,sum;
vector<int> G[MAXN];
bool vis[MAXN]; 
int dfs(int x){
	vis[x]=sum=1,tot=0;
	for(auto i:G[x]){
		if(!vis[i]){
			int t=dfs(i);
			tot=max(tot,t);
			sum+=tot;
		}
	}
	tot=max(tot,n-sum-1);
	ans=min(ans,tot);
	return sum;
}
signed main(){
	cin>>n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		G[x].pb(y),G[y].pb(x);
	}
	dfs(1);
	cout<<ans;
	return 0;
}

DKX

2023-08-10 18:32:04

#pragma GCC optimize(2,3,"Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<vector>
//#include<limit>
#define int long long
#define pb push_back
using namespace std;
const int MAXN=1e5+5;
int n,tot,ans=INT_MAX,sum;
vector<int> G[MAXN];
bool vis[MAXN]; 
int dfs(int x){
	vis[x]=sum=1,tot=0;
	for(auto i:G[x]){
		if(!vis[i]){
			int t=dfs(i);
			tot=max(tot,t);
			sum+=tot;
		}
	}
	tot=max(tot,n-sum-1);
	ans=min(ans,tot);
	return sum;
}
signed main(){
	cin>>n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		G[x].pb(y),G[y].pb(x);
	}
	dfs(1);
	cout<<ans;
	return 0;
}

1

共 2 条回复