oj.uz

Submission #956091

# Submission time Handle Problem Language Result Execution time Memory
956091 2024-04-01T03:52:58 Z Trisanu_Das Burza (COCI16_burza) C++17
160 / 160
 385 ms 281676 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();
		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";
}

Compilation message

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

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 96024 KB Output is correct
2 Correct 298 ms 97052 KB Output is correct
3 Correct 269 ms 12764 KB Output is correct
4 Correct 338 ms 232460 KB Output is correct
5 Correct 334 ms 242804 KB Output is correct
6 Correct 65 ms 35512 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 84596 KB Output is correct
2 Correct 299 ms 80636 KB Output is correct
3 Correct 266 ms 16892 KB Output is correct
4 Correct 270 ms 6632 KB Output is correct
5 Correct 292 ms 82688 KB Output is correct
6 Correct 331 ms 276376 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 82544 KB Output is correct
2 Correct 284 ms 84716 KB Output is correct
3 Correct 268 ms 13632 KB Output is correct
4 Correct 358 ms 271448 KB Output is correct
5 Correct 265 ms 172976 KB Output is correct
6 Correct 67 ms 41556 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 125048 KB Output is correct
2 Correct 299 ms 99072 KB Output is correct
3 Correct 261 ms 12784 KB Output is correct
4 Correct 321 ms 236520 KB Output is correct
5 Correct 204 ms 146320 KB Output is correct
6 Correct 54 ms 25092 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 70404 KB Output is correct
2 Correct 280 ms 80468 KB Output is correct
3 Correct 307 ms 12884 KB Output is correct
4 Correct 353 ms 209236 KB Output is correct
5 Correct 334 ms 240756 KB Output is correct
6 Correct 221 ms 174956 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 88836 KB Output is correct
2 Correct 295 ms 76832 KB Output is correct
3 Correct 262 ms 12792 KB Output is correct
4 Correct 351 ms 224392 KB Output is correct
5 Correct 313 ms 255948 KB Output is correct
6 Correct 178 ms 150284 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 84736 KB Output is correct
2 Correct 277 ms 80472 KB Output is correct
3 Correct 274 ms 13040 KB Output is correct
4 Correct 331 ms 231108 KB Output is correct
5 Correct 283 ms 74468 KB Output is correct
6 Correct 261 ms 181884 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 94976 KB Output is correct
2 Correct 295 ms 90976 KB Output is correct
3 Correct 261 ms 12880 KB Output is correct
4 Correct 385 ms 242660 KB Output is correct
5 Correct 173 ms 135972 KB Output is correct
6 Correct 318 ms 257144 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 72288 KB Output is correct
2 Correct 292 ms 92756 KB Output is correct
3 Correct 270 ms 14836 KB Output is correct
4 Correct 265 ms 12884 KB Output is correct
5 Correct 179 ms 150356 KB Output is correct
6 Correct 358 ms 211868 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 64252 KB Output is correct
2 Correct 290 ms 93068 KB Output is correct
3 Correct 258 ms 12784 KB Output is correct
4 Correct 352 ms 281676 KB Output is correct
5 Correct 252 ms 68180 KB Output is correct
6 Correct 119 ms 107344 KB Output is correct