oj.uz

답안 #937935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937935 2024-03-04T16:57:00 Z PM1 Burza (COCI16_burza) C++17
160 / 160
 335 ms 281680 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxn=405,mxb=20;
int n,k,st[mxn],fn[mxn],dis[mxn],par[mxn],cnt=0;
vector<int>v[mxn],now,leaf;
bool dp[mxn][(1<<mxb)],ans=0;
void dfs(int z){
	st[z]=++cnt;
	if(dis[z]<=k-1)
		now.push_back(z);
	if(dis[z]==k-1)
		leaf.push_back(st[z]);
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			dis[i]=dis[z]+1;
			dfs(i);
		}
	}
	fn[z]=cnt;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dis[1]=-1;
	dfs(1);
	leaf.push_back(n+1);
	for(auto i:now)
	dp[leaf.size()-1][0]=1;
	for(int i=now.size()-1;i>=1;i--){
		int d=dis[now[i]],l=st[now[i]],r=fn[now[i]]+1;
		int L=lower_bound(leaf.begin(),leaf.end(),l)-leaf.begin();
		int R=lower_bound(leaf.begin(),leaf.end(),r)-leaf.begin();
		//cout<<L <<" "<<R<<'\n';
		for(int w=0;w<(1<<mxb);w++){
			if(w&(1<<d))
				dp[L][w]|=dp[R][w-(1<<d)];
		}
	}
	for(int w=0;w<(1<<mxb);w++)
		ans|=dp[0][w];
	if(ans)
		cout<<"DA";
	else
		cout<<"NE";
	return 0;
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:36:11: warning: unused variable 'i' [-Wunused-variable]
   36 |  for(auto i:now)
      |           ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 258 ms 98896 KB Output is correct
2 Correct 295 ms 96852 KB Output is correct
3 Correct 263 ms 12880 KB Output is correct
4 Correct 335 ms 232544 KB Output is correct
5 Correct 299 ms 242768 KB Output is correct
6 Correct 63 ms 35312 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 85184 KB Output is correct
2 Correct 299 ms 80464 KB Output is correct
3 Correct 288 ms 16980 KB Output is correct
4 Correct 278 ms 6636 KB Output is correct
5 Correct 304 ms 82512 KB Output is correct
6 Correct 302 ms 276232 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 296 ms 82488 KB Output is correct
2 Correct 278 ms 84732 KB Output is correct
3 Correct 277 ms 13652 KB Output is correct
4 Correct 314 ms 271524 KB Output is correct
5 Correct 235 ms 172884 KB Output is correct
6 Correct 75 ms 41552 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 304 ms 127876 KB Output is correct
2 Correct 307 ms 99152 KB Output is correct
3 Correct 261 ms 12880 KB Output is correct
4 Correct 295 ms 236880 KB Output is correct
5 Correct 193 ms 146256 KB Output is correct
6 Correct 56 ms 25168 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 70236 KB Output is correct
2 Correct 284 ms 80436 KB Output is correct
3 Correct 268 ms 12792 KB Output is correct
4 Correct 326 ms 250640 KB Output is correct
5 Correct 314 ms 240612 KB Output is correct
6 Correct 210 ms 174928 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 88656 KB Output is correct
2 Correct 287 ms 76372 KB Output is correct
3 Correct 267 ms 12788 KB Output is correct
4 Correct 318 ms 224172 KB Output is correct
5 Correct 276 ms 255876 KB Output is correct
6 Correct 181 ms 150352 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 84732 KB Output is correct
2 Correct 276 ms 80668 KB Output is correct
3 Correct 260 ms 12776 KB Output is correct
4 Correct 304 ms 231248 KB Output is correct
5 Correct 285 ms 74508 KB Output is correct
6 Correct 237 ms 181844 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 95344 KB Output is correct
2 Correct 289 ms 90876 KB Output is correct
3 Correct 261 ms 12880 KB Output is correct
4 Correct 306 ms 242768 KB Output is correct
5 Correct 187 ms 135908 KB Output is correct
6 Correct 300 ms 257012 KB Output is correct

Subtask #9
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 72272 KB Output is correct
2 Correct 301 ms 92984 KB Output is correct
3 Correct 261 ms 14848 KB Output is correct
4 Correct 274 ms 12788 KB Output is correct
5 Correct 191 ms 150352 KB Output is correct
6 Correct 281 ms 211792 KB Output is correct

Subtask #10
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 251 ms 64248 KB Output is correct
2 Correct 286 ms 92756 KB Output is correct
3 Correct 276 ms 12780 KB Output is correct
4 Correct 331 ms 281680 KB Output is correct
5 Correct 261 ms 68224 KB Output is correct
6 Correct 118 ms 107344 KB Output is correct