oj.uz

Submission #744205

# Submission time Handle Problem Language Result Execution time Memory
744205 2023-05-18T09:19:04 Z jamezzz Wells (CEOI21_wells) C++17
0 / 100
 189 ms 796 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],p[maxn],rnk[maxn];
vector<int> AL[maxn];

int fp(int i){return p[i]==i?i:p[i]=fp(p[i]);}
void join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return;
	if(rnk[x]<rnk[y])p[x]=y;
	else p[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
}

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;
}

vector<ii> EL;

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);
		EL.pb({a,b});
	}
	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;
	}
	
	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){
			p[i]=i,rnk[i]=1;
			if(bad[i])continue;
			if(dep[i]%k==0)v.pb(i);
			else v2.pb(i);
		}
		for(auto[x,y]:EL){
			if(dep[x]%k!=0&&dep[y]%k!=0)join(x,y);
		}
		//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];
				if(fp(x)!=fp(y))continue;
				mx=max(mx,dist(x,y));
			}
		}
		dbg("	mn: %d, mx: %d\n",mn,mx);
		if(mn>=k&&mx<k-1){
			ll hh=genhh(v);
			s.insert(hh);
			dbg("	good: %d\n",i);
		}
	}
	ll ans=(s.size()*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:92:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  sf("%d%d",&n,&k);
      |    ^
wells.cpp:97:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   int a,b;sf("%d%d",&a,&b);
      |             ^

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Partially correct 169 ms 652 KB Output is partially correct
3 Partially correct 108 ms 796 KB Output is partially correct
4 Correct 117 ms 720 KB Output is correct
5 Partially correct 189 ms 596 KB Output is partially correct
6 Partially correct 72 ms 680 KB Output is partially correct
7 Correct 47 ms 596 KB Output is correct
8 Correct 50 ms 652 KB Output is correct
9 Correct 50 ms 656 KB Output is correct
10 Correct 85 ms 596 KB Output is correct
11 Incorrect 74 ms 656 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Partially correct 169 ms 652 KB Output is partially correct
3 Partially correct 108 ms 796 KB Output is partially correct
4 Correct 117 ms 720 KB Output is correct
5 Partially correct 189 ms 596 KB Output is partially correct
6 Partially correct 72 ms 680 KB Output is partially correct
7 Correct 47 ms 596 KB Output is correct
8 Correct 50 ms 652 KB Output is correct
9 Correct 50 ms 656 KB Output is correct
10 Correct 85 ms 596 KB Output is correct
11 Incorrect 74 ms 656 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Partially correct 169 ms 652 KB Output is partially correct
3 Partially correct 108 ms 796 KB Output is partially correct
4 Correct 117 ms 720 KB Output is correct
5 Partially correct 189 ms 596 KB Output is partially correct
6 Partially correct 72 ms 680 KB Output is partially correct
7 Correct 47 ms 596 KB Output is correct
8 Correct 50 ms 652 KB Output is correct
9 Correct 50 ms 656 KB Output is correct
10 Correct 85 ms 596 KB Output is correct
11 Incorrect 74 ms 656 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 552 KB Output is correct
2 Partially correct 169 ms 652 KB Output is partially correct
3 Partially correct 108 ms 796 KB Output is partially correct
4 Correct 117 ms 720 KB Output is correct
5 Partially correct 189 ms 596 KB Output is partially correct
6 Partially correct 72 ms 680 KB Output is partially correct
7 Correct 47 ms 596 KB Output is correct
8 Correct 50 ms 652 KB Output is correct
9 Correct 50 ms 656 KB Output is correct
10 Correct 85 ms 596 KB Output is correct
11 Incorrect 74 ms 656 KB Output isn't correct
12 Halted 0 ms 0 KB -