| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 743913 |
2023-05-18T06:05:39 Z |
maomao90 |
Wells (CEOI21_wells) |
C++17 |
|
23 ms |
35668 KB |
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1500005;
const int MOD = 1000000007;
int n, k;
vi adj[MAXN];
int d[MAXN], mxd[MAXN];
bool pos;
bool dfs(int u, int p) {
mxd[u] = d[u];
bool res = d[u] % k == 0;
int cnt = 0;
int mx = -INF, smx = -INF, cmx = -INF, csmx = -INF;
for (int v : adj[u]) {
if (v == p) {
continue;
}
d[v] = d[u] + 1;
bool tmp = dfs(v, u);
if (!pos) {
return 0;
}
res |= tmp;
cnt += tmp;
mxto(mxd[u], mxd[v]);
int x = mxd[v] - d[u];
if (tmp) {
x = k - d[u] % k - 1;
}
if (x >= mx) {
smx = mx;
mx = x;
} else {
mxto(smx, x);
}
if (tmp) {
if (mxd[v] >= cmx) {
csmx = cmx;
cmx = mxd[v];
} else {
mxto(csmx, mxd[v]);
}
}
}
if (cnt >= 2 && 2 * d[u] % k != 0 && cmx + csmx - 2 * d[u] + 1 >= k) {
pos = 0;
return 0;
}
if (d[u] % k != 0 && mx + smx + 1 >= k) {
pos = 0;
return 0;
}
return res;
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> k;
REP (i, 1, n) {
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
REP (i, 1, n + 1) {
d[i] = 0;
pos = 1;
dfs(i, -1);
if (pos) {
cerr << i << '\n';
cout << "YES\n";
cout << 0 << '\n';
return 0;
}
}
cout << "NO\n";
cout << 0 << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
18 ms |
35496 KB |
Output is partially correct |
| 2 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 3 |
Partially correct |
18 ms |
35564 KB |
Output is partially correct |
| 4 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 5 |
Partially correct |
19 ms |
35540 KB |
Output is partially correct |
| 6 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 7 |
Correct |
19 ms |
35456 KB |
Output is correct |
| 8 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 9 |
Partially correct |
17 ms |
35524 KB |
Output is partially correct |
| 10 |
Correct |
18 ms |
35540 KB |
Output is correct |
| 11 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 12 |
Partially correct |
17 ms |
35500 KB |
Output is partially correct |
| 13 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 14 |
Partially correct |
20 ms |
35460 KB |
Output is partially correct |
| 15 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 16 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 17 |
Partially correct |
17 ms |
35556 KB |
Output is partially correct |
| 18 |
Partially correct |
17 ms |
35532 KB |
Output is partially correct |
| 19 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 20 |
Correct |
19 ms |
35548 KB |
Output is correct |
| 21 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 22 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 23 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 24 |
Partially correct |
18 ms |
35572 KB |
Output is partially correct |
| 25 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 26 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 27 |
Partially correct |
23 ms |
35536 KB |
Output is partially correct |
| 28 |
Correct |
17 ms |
35472 KB |
Output is correct |
| 29 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 30 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 31 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 32 |
Correct |
19 ms |
35460 KB |
Output is correct |
| 33 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 34 |
Correct |
20 ms |
35496 KB |
Output is correct |
| 35 |
Partially correct |
19 ms |
35668 KB |
Output is partially correct |
| 36 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 37 |
Partially correct |
20 ms |
35504 KB |
Output is partially correct |
| 38 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 39 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 40 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 41 |
Partially correct |
18 ms |
35452 KB |
Output is partially correct |
| 42 |
Partially correct |
18 ms |
35524 KB |
Output is partially correct |
| 43 |
Partially correct |
21 ms |
35468 KB |
Output is partially correct |
| 44 |
Correct |
23 ms |
35452 KB |
Output is correct |
| 45 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 46 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 47 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 48 |
Partially correct |
18 ms |
35548 KB |
Output is partially correct |
| 49 |
Incorrect |
19 ms |
35540 KB |
Output isn't correct |
| 50 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
18 ms |
35496 KB |
Output is partially correct |
| 2 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 3 |
Partially correct |
18 ms |
35564 KB |
Output is partially correct |
| 4 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 5 |
Partially correct |
19 ms |
35540 KB |
Output is partially correct |
| 6 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 7 |
Correct |
19 ms |
35456 KB |
Output is correct |
| 8 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 9 |
Partially correct |
17 ms |
35524 KB |
Output is partially correct |
| 10 |
Correct |
18 ms |
35540 KB |
Output is correct |
| 11 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 12 |
Partially correct |
17 ms |
35500 KB |
Output is partially correct |
| 13 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 14 |
Partially correct |
20 ms |
35460 KB |
Output is partially correct |
| 15 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 16 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 17 |
Partially correct |
17 ms |
35556 KB |
Output is partially correct |
| 18 |
Partially correct |
17 ms |
35532 KB |
Output is partially correct |
| 19 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 20 |
Correct |
19 ms |
35548 KB |
Output is correct |
| 21 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 22 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 23 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 24 |
Partially correct |
18 ms |
35572 KB |
Output is partially correct |
| 25 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 26 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 27 |
Partially correct |
23 ms |
35536 KB |
Output is partially correct |
| 28 |
Correct |
17 ms |
35472 KB |
Output is correct |
| 29 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 30 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 31 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 32 |
Correct |
19 ms |
35460 KB |
Output is correct |
| 33 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 34 |
Correct |
20 ms |
35496 KB |
Output is correct |
| 35 |
Partially correct |
19 ms |
35668 KB |
Output is partially correct |
| 36 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 37 |
Partially correct |
20 ms |
35504 KB |
Output is partially correct |
| 38 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 39 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 40 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 41 |
Partially correct |
18 ms |
35452 KB |
Output is partially correct |
| 42 |
Partially correct |
18 ms |
35524 KB |
Output is partially correct |
| 43 |
Partially correct |
21 ms |
35468 KB |
Output is partially correct |
| 44 |
Correct |
23 ms |
35452 KB |
Output is correct |
| 45 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 46 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 47 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 48 |
Partially correct |
18 ms |
35548 KB |
Output is partially correct |
| 49 |
Incorrect |
19 ms |
35540 KB |
Output isn't correct |
| 50 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
18 ms |
35496 KB |
Output is partially correct |
| 2 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 3 |
Partially correct |
18 ms |
35564 KB |
Output is partially correct |
| 4 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 5 |
Partially correct |
19 ms |
35540 KB |
Output is partially correct |
| 6 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 7 |
Correct |
19 ms |
35456 KB |
Output is correct |
| 8 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 9 |
Partially correct |
17 ms |
35524 KB |
Output is partially correct |
| 10 |
Correct |
18 ms |
35540 KB |
Output is correct |
| 11 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 12 |
Partially correct |
17 ms |
35500 KB |
Output is partially correct |
| 13 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 14 |
Partially correct |
20 ms |
35460 KB |
Output is partially correct |
| 15 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 16 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 17 |
Partially correct |
17 ms |
35556 KB |
Output is partially correct |
| 18 |
Partially correct |
17 ms |
35532 KB |
Output is partially correct |
| 19 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 20 |
Correct |
19 ms |
35548 KB |
Output is correct |
| 21 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 22 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 23 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 24 |
Partially correct |
18 ms |
35572 KB |
Output is partially correct |
| 25 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 26 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 27 |
Partially correct |
23 ms |
35536 KB |
Output is partially correct |
| 28 |
Correct |
17 ms |
35472 KB |
Output is correct |
| 29 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 30 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 31 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 32 |
Correct |
19 ms |
35460 KB |
Output is correct |
| 33 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 34 |
Correct |
20 ms |
35496 KB |
Output is correct |
| 35 |
Partially correct |
19 ms |
35668 KB |
Output is partially correct |
| 36 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 37 |
Partially correct |
20 ms |
35504 KB |
Output is partially correct |
| 38 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 39 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 40 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 41 |
Partially correct |
18 ms |
35452 KB |
Output is partially correct |
| 42 |
Partially correct |
18 ms |
35524 KB |
Output is partially correct |
| 43 |
Partially correct |
21 ms |
35468 KB |
Output is partially correct |
| 44 |
Correct |
23 ms |
35452 KB |
Output is correct |
| 45 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 46 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 47 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 48 |
Partially correct |
18 ms |
35548 KB |
Output is partially correct |
| 49 |
Incorrect |
19 ms |
35540 KB |
Output isn't correct |
| 50 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
18 ms |
35496 KB |
Output is partially correct |
| 2 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 3 |
Partially correct |
18 ms |
35564 KB |
Output is partially correct |
| 4 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 5 |
Partially correct |
19 ms |
35540 KB |
Output is partially correct |
| 6 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 7 |
Correct |
19 ms |
35456 KB |
Output is correct |
| 8 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 9 |
Partially correct |
17 ms |
35524 KB |
Output is partially correct |
| 10 |
Correct |
18 ms |
35540 KB |
Output is correct |
| 11 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 12 |
Partially correct |
17 ms |
35500 KB |
Output is partially correct |
| 13 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 14 |
Partially correct |
20 ms |
35460 KB |
Output is partially correct |
| 15 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 16 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 17 |
Partially correct |
17 ms |
35556 KB |
Output is partially correct |
| 18 |
Partially correct |
17 ms |
35532 KB |
Output is partially correct |
| 19 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 20 |
Correct |
19 ms |
35548 KB |
Output is correct |
| 21 |
Partially correct |
18 ms |
35552 KB |
Output is partially correct |
| 22 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 23 |
Partially correct |
17 ms |
35540 KB |
Output is partially correct |
| 24 |
Partially correct |
18 ms |
35572 KB |
Output is partially correct |
| 25 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 26 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 27 |
Partially correct |
23 ms |
35536 KB |
Output is partially correct |
| 28 |
Correct |
17 ms |
35472 KB |
Output is correct |
| 29 |
Partially correct |
21 ms |
35540 KB |
Output is partially correct |
| 30 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 31 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 32 |
Correct |
19 ms |
35460 KB |
Output is correct |
| 33 |
Partially correct |
18 ms |
35492 KB |
Output is partially correct |
| 34 |
Correct |
20 ms |
35496 KB |
Output is correct |
| 35 |
Partially correct |
19 ms |
35668 KB |
Output is partially correct |
| 36 |
Partially correct |
18 ms |
35504 KB |
Output is partially correct |
| 37 |
Partially correct |
20 ms |
35504 KB |
Output is partially correct |
| 38 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 39 |
Partially correct |
20 ms |
35540 KB |
Output is partially correct |
| 40 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 41 |
Partially correct |
18 ms |
35452 KB |
Output is partially correct |
| 42 |
Partially correct |
18 ms |
35524 KB |
Output is partially correct |
| 43 |
Partially correct |
21 ms |
35468 KB |
Output is partially correct |
| 44 |
Correct |
23 ms |
35452 KB |
Output is correct |
| 45 |
Partially correct |
18 ms |
35568 KB |
Output is partially correct |
| 46 |
Partially correct |
18 ms |
35540 KB |
Output is partially correct |
| 47 |
Partially correct |
19 ms |
35552 KB |
Output is partially correct |
| 48 |
Partially correct |
18 ms |
35548 KB |
Output is partially correct |
| 49 |
Incorrect |
19 ms |
35540 KB |
Output isn't correct |
| 50 |
Halted |
0 ms |
0 KB |
- |
