oj.uz

답안 #744156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744156 2023-05-18T08:45:59 Z jamezzz Wells (CEOI21_wells) C++17
0 / 100
 310 ms 716 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define INF 1023456789
typedef long long ll;
typedef pair<int,int> ii;

#define maxn 10005
#define mod 1000000007

int n,k,dep[maxn],bad[maxn],mxdep[maxn],par[20][maxn];
vector<int> AL[maxn];

void dfs(int u,int p){
	par[0][u]=p;
	for(int k=1;k<20;++k){
		if(par[k-1][u]==-1)par[k][u]=-1;
		else par[k][u]=par[k-1][par[k-1][u]];
	}
	for(int v:AL[u]){
		if(v==p)continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
		mxdep[u]=max(mxdep[u],1+mxdep[v]);
	}
}

void dfs2(int u,int p,int out){
	ii mx={out,p},smx={0,0};
	for(int v:AL[u]){
		if(v==p)continue;
		if(1+mxdep[v]>mx.fi){
			smx=mx;mx={1+mxdep[v],v};
		}
		else if(1+mxdep[v]>smx.fi){
			smx={1+mxdep[v],v};
		}
	}
	if(mx.fi+smx.fi<k-1)bad[u]=1;
	for(int v:AL[u]){
		if(v==p)continue;
		if(v==mx.se)dfs2(v,u,1+smx.fi);
		else dfs2(v,u,1+mx.fi);
	}
}

int lca(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	for(int k=19;k>=0;--k)if(par[k][a]!=-1&&dep[par[k][a]]>=dep[b])a=par[k][a];
	if(a==b)return a;
	for(int k=19;k>=0;--k)if(par[k][a]!=par[k][b])a=par[k][a],b=par[k][b];
	return par[0][a];
}

inline int dist(int a,int b){
	return dep[a]+dep[b]-2*dep[lca(a,b)];
}

mt19937_64 rng(0);
ll num[maxn];
unordered_set<ll> s;

ll genhh(vector<int> &v){
	ll res=0;
	for(int i:v)res^=num[i];
	return res;
}

int main(){
	sf("%d%d",&n,&k);
	
	for(int i=1;i<=n;++i)num[i]=rng();
	
	for(int i=1;i<n;++i){
		int a,b;sf("%d%d",&a,&b);
		AL[a].pb(b);AL[b].pb(a);
	}
	dfs(1,-1);
	dfs2(1,-1,0);
	ll mult=1;
	
	int badcnt=0;
	dbg("bad: ");
	for(int i=1;i<=n;++i){
		dbg("%d ",bad[i]);
		if(bad[i])mult=2*mult%mod;
		badcnt+=bad[i];
	}
	dbg("\n");
	if(badcnt==n){
		pf("YES\n%lld\n",mult);
		return 0;
	}
	
	ll ans=0;
	for(int i=1;i<=n;++i){
		if(bad[i])continue;
		dep[i]=0;
		dfs(i,-1);
		
		vector<int> v,v2;
		
		//put at all 0 mod k
		int mn=INF,mx=0;
		for(int i=1;i<=n;++i){
			if(bad[i])continue;
			if(dep[i]%k==0)v.pb(i);
			else v2.pb(i);
		}
		//condition 1: shortest distance between stuff with 0 mod k must be at least k
		for(int i=0;i<sz(v);++i){
			for(int j=i+1;j<sz(v);++j){
				mn=min(mn,dist(v[i],v[j]));
			}
		}
		//condition 2: longest distance between stuff != 0 mod k, not passing through 0 mod k, must be at most k-1
		for(int i=0;i<sz(v2);++i){
			for(int j=i+1;j<sz(v2);++j){
				int x=v2[i],y=v2[j];
				int l=lca(x,y);
				if(dep[x]-dep[l]>=dep[x]%k||dep[y]-dep[l]>=dep[y]%k)continue;
				mx=max(mx,dep[x]+dep[y]-2*dep[l]);
			}
		}
		dbg("mn: %d, mx: %d\n",mn,mx);
		if(mn>=k&&mx<k-1){
			ll hh=genhh(v);
			if(s.find(hh)!=s.end())continue;
			s.insert(hh);
			++ans;
			dbg("good: %d\n",i);
		}
	}
	ans=(ans*mult)%mod;
	if(ans)pf("YES\n");
	else pf("NO\n");
	pf("%lld\n",ans);
}

Compilation message

wells.cpp: In function 'int main()':
wells.cpp:81:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  sf("%d%d",&n,&k);
      |    ^
wells.cpp:86:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   int a,b;sf("%d%d",&a,&b);
      |             ^

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Partially correct 310 ms 716 KB Output is partially correct
3 Partially correct 225 ms 652 KB Output is partially correct
4 Correct 307 ms 652 KB Output is correct
5 Partially correct 302 ms 636 KB Output is partially correct
6 Partially correct 302 ms 596 KB Output is partially correct
7 Correct 260 ms 640 KB Output is correct
8 Correct 285 ms 636 KB Output is correct
9 Correct 254 ms 656 KB Output is correct
10 Correct 295 ms 648 KB Output is correct
11 Incorrect 221 ms 636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Partially correct 310 ms 716 KB Output is partially correct
3 Partially correct 225 ms 652 KB Output is partially correct
4 Correct 307 ms 652 KB Output is correct
5 Partially correct 302 ms 636 KB Output is partially correct
6 Partially correct 302 ms 596 KB Output is partially correct
7 Correct 260 ms 640 KB Output is correct
8 Correct 285 ms 636 KB Output is correct
9 Correct 254 ms 656 KB Output is correct
10 Correct 295 ms 648 KB Output is correct
11 Incorrect 221 ms 636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Partially correct 310 ms 716 KB Output is partially correct
3 Partially correct 225 ms 652 KB Output is partially correct
4 Correct 307 ms 652 KB Output is correct
5 Partially correct 302 ms 636 KB Output is partially correct
6 Partially correct 302 ms 596 KB Output is partially correct
7 Correct 260 ms 640 KB Output is correct
8 Correct 285 ms 636 KB Output is correct
9 Correct 254 ms 656 KB Output is correct
10 Correct 295 ms 648 KB Output is correct
11 Incorrect 221 ms 636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Partially correct 310 ms 716 KB Output is partially correct
3 Partially correct 225 ms 652 KB Output is partially correct
4 Correct 307 ms 652 KB Output is correct
5 Partially correct 302 ms 636 KB Output is partially correct
6 Partially correct 302 ms 596 KB Output is partially correct
7 Correct 260 ms 640 KB Output is correct
8 Correct 285 ms 636 KB Output is correct
9 Correct 254 ms 656 KB Output is correct
10 Correct 295 ms 648 KB Output is correct
11 Incorrect 221 ms 636 KB Output isn't correct
12 Halted 0 ms 0 KB -