| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 598140 |
2022-07-17T17:19:41 Z |
dxz05 |
Jail (JOI22_jail) |
C++14 |
|
15 ms |
9760 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];
inline bool jail(int n, int m, vector<int> S, vector<int> T){
for (int i = 0; i < m; i++){
for (int j = i + 1; j < m; j++){
if (in(S[i], S[j], T[i]) && in(S[i], T[j], T[i])) return false;
if (in(S[j], S[i], T[j]) && in(S[j], T[i], T[j])) return false;
int x = -1, y = -1;
if (in(S[j], S[i], T[j])) x = S[i];
if (in(S[j], T[i], T[j])) x = T[i];
if (in(S[i], S[j], T[i])) y = S[j];
if (in(S[i], T[j], T[i])) y = T[j];
if (x == -1 && y == -1) continue;
bool ok = false;
if (x == -1){
gg[i].push_back(j);
ok = true;
}
if (y == -1){
gg[j].push_back(i);
ok = true;
}
if (x == y){
if (x == S[i]) gg[i].push_back(j); else
gg[j].push_back(i);
ok = true;
}
if (x == S[i] && y == T[j]){
gg[i].push_back(j);
ok = true;
}
if (x == T[i] && y == S[j]){
gg[j].push_back(i);
ok = true;
}
// if (!ok) return false;
}
}
return true;
}
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);
for (int i = 0; i < m; i++){
cin >> S[i] >> T[i];
S[i]--, T[i]--;
}
for (int i = 0; i < m; i++){
gg[i].clear();
color[i] = 0;
}
if (!jail(n, m, S, T)){
cout << "No\n";
return;
}
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;
}
Compilation message
jail.cpp: In function 'bool jail(int, int, std::vector<int>, std::vector<int>)':
jail.cpp:98:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
98 | bool ok = false;
| ^~
| # |
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 |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
9684 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9760 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9712 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9760 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9712 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9760 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9712 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9760 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9712 KB |
Output isn't correct |
| 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 |
9676 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 5 |
Incorrect |
11 ms |
9684 KB |
Output isn't correct |
| 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 |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
9684 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
