| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 951098 |
2024-03-21T06:45:15 Z |
hotboy2703 |
Jail (JOI22_jail) |
C++14 |
|
68 ms |
122400 KB |
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll n,m;
const ll MAXN = 1.2e5;
const ll MAXK = 17;
ll cur_node;
namespace CYC{
vector <ll> g[MAXN*MAXK*2 + MAXN * 5 + 100];
void add_edge(ll u,ll v){g[u].push_back(v);}
bool in[MAXN*MAXK*2 + MAXN * 5 + 100];
bool in_st[MAXN*MAXK*2 + MAXN * 5 + 100];
bool detect_cycle;
void init(){
for (ll i = 1;i <= cur_node;i++){g[i].clear();in[i] = 0;in_st[i] = 0;}
detect_cycle = 0;
}
ll depth=0;
ll cnt = 0;
void dfs(ll u){
// cout<<u<<' '<<depth<<' '<<cnt<<endl;
// depth++;
// cnt++;
in_st[u] = 1;
in[u] = 1;
for (auto v:g[u]){
if (in_st[v])detect_cycle = 1;
if (in[v])continue;
dfs(v);
}
in_st[u] = 0;
// depth--;
}
void solve(){
for (ll i = 1;i <= cur_node;i++)if (!in[i])dfs(i);
}
}
vector <ll> g[MAXN+100];
ll sp[MAXK][MAXN+100];
ll node[MAXK][MAXN+100];
ll path[MAXN+100][2];
ll depth[MAXN+100];
ll lca(ll u,ll v){
if (depth[u] > depth[v])swap(u,v);
for (ll j = MAXK-1;j>=0;j--){
if (depth[sp[j][v]]>=depth[u])v=sp[j][v];
}
if (v==u)return u;
for (ll j = MAXK-1;j>=0;j--){
if (sp[j][v] != sp[j][u]){
v=sp[j][v];
u=sp[j][u];
}
}
return sp[0][u];
}
void dfs(ll u,ll p){
sp[0][u] = p;
depth[u] = depth[p]+1;
for (auto v:g[u]){
if (v==p)continue;
dfs(v,u);
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
freopen("code1.inp","r",stdin);
ll t;
cin>>t;
while (t--){
cin>>n;
for (ll i = 1;i <= n; i++){
g[i].clear();
}
for (ll i = 1;i < n;i ++){
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
cin>>m;
for (ll i = 1;i <= m;i ++){
ll s,t;
cin>>s>>t;
path[i][0] = s,path[i][1] = t;
}
dfs(1,1);
for (ll j = 1;j < MAXK;j ++){
for (ll i = 1;i <= n;i ++){
sp[j][i] = sp[j-1][sp[j-1][i]];
// cout<<sp[j][i]<<' ';
}
// cout<<'\n';
}
// exit(0);
vector <pll> edge[2];
cur_node = m + 1;
for (ll k = 0;k < 2;k ++){
for (ll i = 1;i <= n;i ++){
node[0][i] = cur_node++;
}
for (ll j = 1;j < MAXK;j ++){
for (ll i = 1;i <= n;i ++){
node[j][i] = cur_node++;
edge[k].push_back(MP(node[j][i],node[j-1][i]));
edge[k].push_back(MP(node[j][i],node[j-1][sp[j-1][i]]));
}
}
for (ll i = 1;i <= m;i ++){
edge[k].push_back(MP(node[0][path[i][k]],i));
}
for (ll i = 1;i <= m;i ++){
ll u = path[i][0],v = path[i][1];
ll x = lca(u,v);
// cout<<u<<' '<<v<<' '<<x<<'\n';
bool no_lca = 0;
if (k==0){
if (u != x)u = sp[0][u];
else no_lca = 1;
}
if (k==1){
if (v != x)v = sp[0][v];
else no_lca = 1;
}
for (ll j = MAXK-1;j>=0;j--){
if (depth[u]-MASK(j) >= depth[x]){
// cout<<"U "<<i<<' '<<j<<'\n';
edge[k].push_back(MP(i,node[j][u]));
u = sp[j][u];
}
if (depth[v]-MASK(j) >= depth[x]){
// cout<<"V "<<i<<' '<<j<<'\n';
edge[k].push_back(MP(i,node[j][v]));
v = sp[j][v];
}
}
if (!no_lca)edge[k].push_back(MP(i,node[0][x]));
}
}
CYC::init();
for (ll j = 0;j < 2;j ++){
for (auto x:edge[j]){
if (j)swap(x.fi,x.se);
CYC::add_edge(x.fi,x.se);
}
}
// exit(0);
// cout<<cur_node<<endl;
// exit(0);
CYC::solve();
cout<<(CYC::detect_cycle?"No":"Yes")<<'\n';
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | freopen("code1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
122400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
122184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
122184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
122184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
122184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
122228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
122400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
