| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 713398 |
2023-03-21T21:40:00 Z |
mraron |
Jail (JOI22_jail) |
C++14 |
|
147 ms |
908 KB |
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#define ins insert
#ifndef ONLINE_JUDGE
# define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
# define LOG(x) ((void)0)
#endif
using ll = long long;
using ull = unsigned long long ;
using ld = long double ;
using str = string;
using ordered_set=tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;
const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);
template<typename T> T getint() {
T val=0;
char c;
bool neg=false;
while((c=gc()) && !(c>='0' && c<='9')) {
neg|=c=='-';
}
do {
val=(val*10)+c-'0';
} while((c=gc()) && (c>='0' && c<='9'));
return val*(neg?-1:1);
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)
template<int L=20>
struct lca {
int n, lg;
vector<int> par, lvl, ssz;
vector<array<int,L>> dp;
vector<vector<int>> adj;
lca(int n) : n(n), lg(ceil(log2(n))), par(n, -1), lvl(n), ssz(n), dp(n), adj(n) {}
void add_edge(int x, int y) {
adj[x].pb(y);
adj[y].pb(x);
}
void dfs(int x) {
ssz[x]=1;
for(auto i:adj[x]) {
if(!ssz[i]) {
par[i]=x;
lvl[i]=lvl[x]+1;
dfs(i);
ssz[x]+=ssz[i];
}
}
}
void init(int root=0) {
dfs(root);
for(int i=1;i<n;++i) {
fill(all(dp[i]), -1);
}
for(int i=1;i<n;++i) {
dp[i][0]=par[i];
}
for(int j=1;j<lg;++j) {
for(int i=1;i<n;++i) {
if(dp[i][j-1]!=-1) {
dp[i][j]=dp[dp[i][j-1]][j-1];
}
}
}
}
int query(int p, int q) {
if(p==q) return p;
if(lvl[p]>lvl[q]) swap(p,q);
for(int i=lg-1;i>=0;i--) {
if(dp[q][i]!=-1 && lvl[p]<=lvl[dp[q][i]]) q=dp[q][i];
}
if(p==q) return p;
for(int i=lg-1;i>=0;i--) {
if(dp[q][i]!=-1 && dp[q][i]!=dp[p][i]) {
p=dp[p][i];
q=dp[q][i];
}
}
return dp[p][0];
}
pair<int,int> query2(int& a, int& b) {
int p=a, q=b;
if(lvl[p]>lvl[q]){
swap(p,q);
swap(a,b);
}
for(int i=lg-1;i>=0;i--) {
if(dp[q][i]!=-1 && lvl[p]<lvl[dp[q][i]]) q=dp[q][i];
}
if(lvl[p]!=lvl[q]) {
if(p==par[q]) return {q,q};
q=par[q];
}
assert(lvl[p]==lvl[q]);
for(int i=lg-1;i>=0;i--) {
if(dp[q][i]!=-1 && dp[q][i]!=dp[p][i]) {
p=dp[p][i];
q=dp[q][i];
}
}
return {p,q};
}
int kth(int p, int k) {
for(int i=0;i<lg;++i) {
if(k&(1<<i)) {
p=dp[p][i];
}
}
return p;
}
int dist(int a, int b) {
int l=query(a,b);
return lvl[a]+lvl[b]-2*lvl[l];
}
};
const int LG=17;
void dfs(int x, int& cnt, vector<int>& indeg, vector<vector<int>>& adj, vector<bool>& volt) {
cnt++;
volt[x]=1;
for(auto i:adj[x]) {
indeg[i]--;
if(indeg[i]==0) dfs(i, cnt, indeg, adj, volt);
}
}
int main() {
IO;
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
lca<LG> l(n+1);
for(int i=1;i<n;++i) {
int a,b;
cin>>a>>b;
l.add_edge(a, b);
}
l.init(1);
int m;
cin>>m;
vector<pair<int,int>> lst(m);
for(int i=0;i<m;++i) {
cin>>lst[i].xx>>lst[i].yy;
}
vector<array<pair<int,int>,LG>> idx(n+1);
int nxt=m;
for(int i=1;i<=n;++i) {
for(int j=0;j<LG;++j) {
idx[i][j].xx=nxt++;
idx[i][j].yy=nxt++;
}
}
vector<vector<int>> adj(nxt);
vector<int> indeg(nxt);
auto add_edge=[&](int a, int b, bool rev=false) {
if(rev) swap(a,b);
indeg[b]++;
adj[a].pb(b);
//~ cerr<<a<<" "<<b<<"\n";
};
for(int i=1;i<=n;++i) {
for(int j=1;j<LG;++j) {
if(l.dp[i][j-1]!=-1) add_edge(idx[l.dp[i][j-1]][j-1].xx, idx[i][j].xx);
add_edge(idx[i][j-1].xx, idx[i][j].xx);
if(l.dp[i][j-1]!=-1) add_edge(idx[l.dp[i][j-1]][j-1].yy, idx[i][j].yy, true);
add_edge(idx[i][j-1].yy, idx[i][j].yy, true);
}
}
for(int i=0;i<m;++i) {
int from=lst[i].xx, to=lst[i].yy;
//~ cerr<<i<<" "<<idx[from][0].yy<<"\n";
add_edge(i, idx[from][0].xx);
add_edge(i, idx[to][0].yy, true);
int os=l.query(from, to);
if(os!=from) {
from=l.par[from];
}else {
from=l.query2(from, to).yy;
}
//~ cerr<<from<<" "<<to<<"!!\n";
os=l.query(from, to);
for(int j=LG-1;j>=0;j--) {
if(l.dp[from][j]!=-1 && l.lvl[l.dp[from][j]]>=l.lvl[os]) {
add_edge(idx[from][j].xx, i);
from=l.dp[from][j];
}
}
for(int j=LG-1;j>=0;j--) {
if(l.dp[to][j]!=-1 && l.lvl[l.dp[to][j]]>=l.lvl[os]) {
add_edge(idx[to][j].xx, i);
from=l.dp[to][j];
}
}
add_edge(idx[os][0].xx, i);
from=lst[i].xx; to=lst[i].yy;
os=l.query(from, to);
if(os!=to) {
to=l.par[to];
}else {
to=l.query2(to, from).yy;
}
//~ cerr<<from<<" "<<to<<"??\n";
os=l.query(from, to);
for(int j=LG-1;j>=0;j--) {
if(l.dp[from][j]!=-1 && l.lvl[l.dp[from][j]]>=l.lvl[os]) {
add_edge(idx[from][j].yy, i, true);
from=l.dp[from][j];
}
}
for(int j=LG-1;j>=0;j--) {
if(l.dp[to][j]!=-1 && l.lvl[l.dp[to][j]]>=l.lvl[os]) {
add_edge(idx[to][j].yy, i, true);
from=l.dp[to][j];
}
}
add_edge(idx[os][0].yy, i, true);
}
vector<bool> volt(nxt);
int cnt=0;
for(int i=0;i<nxt;++i) {
if(indeg[i]==0 && !volt[i]) dfs(i, cnt, indeg, adj, volt);
}
//~ LOG(cnt);
cout<<(cnt==nxt?"Yes":"No")<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
147 ms |
908 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
852 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
852 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
852 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
852 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
70 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
147 ms |
908 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
