| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 601333 |
2022-07-21T17:53:28 Z |
dxz05 |
Jail (JOI22_jail) |
C++14 |
|
14 ms |
19668 KB |
//#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << "[" << H << "]";
debug_out(T...);
}
#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
clock_t startTime;
double getCurrentTime() {
return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e5 + 3e2;
const int M = 5555;
vector<int> g[N];
int tin[N], tout[N], timer = 0;
int up[N][18], depth[N];
inline void dfs(int v, int p){
tin[v] = ++timer;
depth[v] = depth[p] + 1;
up[v][0] = p;
for (int i = 1; i < 18; i++){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (int u : g[v]){
if (u != p) dfs(u, v);
}
tout[v] = ++timer;
}
inline bool upper(int u, int v){
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
inline int lca(int u, int v){
if (upper(u, v)) return u;
if (upper(v, u)) return v;
for (int i = 17; i >= 0; i--){
if (!upper(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
inline int dist(int u, int v){
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
inline bool in(int a, int b, int c){
return dist(a, c) == dist(a, b) + dist(b, c);
}
vector<int> gg[N];
int color[N];
bool dfs(int v){
color[v] = 1;
for (int u : gg[v]){
if (color[u] == 1) return true;
if (color[u] == 0 && dfs(u)) return true;
}
color[v] = 2;
return false;
}
void solve(int TC) {
int n;
cin >> n;
timer = 0;
for (int i = 0; i < n; i++) g[i].clear();
for (int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
--a, --b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0, 0);
int m;
cin >> m;
vector<int> S(m), T(m);
vector<int> ids(n, -1), idt(n, -1);
for (int i = 0; i < m; i++){
cin >> S[i] >> T[i];
S[i]--, T[i]--;
ids[S[i]] = i;
idt[T[i]] = i;
}
if (depth[n - 1] == n){
vector<int> left(n, 0), right(n, 0);
for (int i = 0; i < n; i++){
if (S[i] < T[i]){
right[S[i]]++;
right[T[i]]--;
} else {
left[T[i]]++;
left[S[i]]--;
}
}
for (int i = 1; i < n; i++) left[i] += left[i - 1], right[i] += right[i - 1];
for (int i = 0; i < n; i++){
if (left[i] && right[i]){
cout << "No\n";
return;
}
}
cout << "Yes\n";
return;
}
for (int i = 0; i < m; i++){
gg[i].clear();
color[i] = 0;
}
for (int i = 0; i < m; i++){
int s = S[i], t = T[i];
int l = lca(s, t);
int mask = 0;
while (upper(l, s)){
int j = ids[s];
if (j != -1 && j != i) gg[j].push_back(i), mask |= 1;
j = idt[s];
if (j != -1 && j != i) gg[i].push_back(j), mask |= 2;
if (s == 0 || mask == 3) break;
s = up[s][0];
}
mask = 0;
while (upper(l, t)){
int j = ids[t];
if (j != -1 && j != i) gg[j].push_back(i), mask |= 1;
j = idt[t];
if (j != -1 && j != i) gg[i].push_back(j), mask |= 2;
if (t == 0 || mask == 3) break;
t = up[t][0];
}
}
for (int i = 0; i < m; i++){
if (color[i] == 0 && dfs(i)){
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
int main() {
startTime = clock();
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#ifdef dddxxz
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int TC = 1;
cin >> TC;
for (int test = 1; test <= TC; test++) {
//debug(test);
//cout << "Case #" << test << ": ";
solve(test);
}
#ifdef dddxxz
cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9656 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Runtime error |
13 ms |
19648 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
13 ms |
19668 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
13 ms |
19668 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
13 ms |
19668 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Runtime error |
13 ms |
19668 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9752 KB |
Output is correct |
| 5 |
Runtime error |
14 ms |
19540 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9656 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Runtime error |
13 ms |
19648 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
