# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
955738 |
2024-03-31T11:29:58 Z |
TimAni |
Burza (COCI16_burza) |
C++17 |
|
361 ms |
15928 KB |
//Some wierd BFS can also pass(?)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define siz(x) (int)x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
//===========================================
const int MAX = 405;
vi adj[MAX];
int p[MAX], dep[MAX], depb[MAX];
set<vi> vis;
void dfs(int v){
for (int u: adj[v]){
if (u == p[v]) continue;
p[u] = v;
dep[u] = dep[v]+1;
dfs(u);
depb[v] = max(depb[v], depb[u]+1);
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
for (int i = 1; i < n; i++){
int a, b; cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1);
queue<vi> q; q.push({1});
while (siz(q)){
auto vec = q.front(); q.pop();
if (vec.empty()){
cout << "DA\n";
return 0;
}
int rem = k-dep[vec[0]];
vi vv;
for (int v: vec){
for (int u: adj[v]){
if (u == p[v]) continue;
if (depb[u]+1 >= rem) vv.pb(u);
}
}
if (siz(vv) > rem) continue;
for (int i = 0; i < siz(vv); i++){
swap(vv[i], vv.back());
vector<int> temp = vv; temp.pop_back(); sort(all(temp));
if (!vis.count(temp)){
q.push(temp);
vis.insert(temp);
}
swap(vv[i], vv.back());
}
}
cout << "NE\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
2308 KB |
Output is correct |
2 |
Correct |
341 ms |
15420 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
345 ms |
15388 KB |
Output is correct |
2 |
Correct |
361 ms |
15696 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
338 ms |
15492 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
15388 KB |
Output is correct |
2 |
Correct |
343 ms |
15444 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
4124 KB |
Output is correct |
2 |
Correct |
356 ms |
15496 KB |
Output is correct |
3 |
Correct |
1 ms |
500 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
340 ms |
15508 KB |
Output is correct |
2 |
Correct |
357 ms |
15696 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
15440 KB |
Output is correct |
2 |
Correct |
347 ms |
15424 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
345 ms |
15452 KB |
Output is correct |
2 |
Correct |
352 ms |
15456 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
350 ms |
15928 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
4092 KB |
Output is correct |
2 |
Correct |
346 ms |
15444 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
2140 KB |
Output is correct |
2 |
Correct |
337 ms |
15472 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
576 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
152 ms |
7840 KB |
Output is correct |
2 |
Correct |
350 ms |
15372 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
150 ms |
7764 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |