oj.uz

Submission #874457

# Submission time Handle Problem Language Result Execution time Memory
874457 2023-11-17T04:50:39 Z winter0101 Jail (JOI22_jail) C++14
0 / 100
 5000 ms 32112 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=1e5+2e4+9;
vector<int>a[maxn];
pii b[maxn];
int st[maxn][17];
int d[maxn];
void dfs(int u,int par){
for (auto v:a[u]){
if (v==par)continue;
st[v][0]=u;
for1(i,1,17)st[v][i]=st[st[v][i-1]][i-1];
d[v]=d[u]+1;
dfs(v,u);
}
}
int lca(int u,int v){
if (d[u]<d[v])swap(u,v);
int k=d[u]-d[v];
for1(i,0,17)if (k>>i&1)u=st[u][i];
if (u==v)return u;
for2(i,17,0){
if (!st[u][i]||!st[v][i])continue;
if (st[u][i]!=st[v][i]){
    u=st[u][i];
    v=st[v][i];
}
}
return st[u][0];
}
bool onpath(int u,int v,int k){
int t=lca(u,v);
if (lca(t,k)==t&&lca(k,u)==k)return 1;
if (lca(t,k)==t&&lca(k,v)==k)return 1;
return 0;
}
vector<int>g[maxn];
int scc=0;
int low[maxn],num[maxn],tme=0;
stack<int>t;
void redfs(int u){
t.push(u);
low[u]=num[u]=++tme;
for (auto v:g[u]){
if (num[v]==-1)continue;
if (num[v])low[u]=min(low[u],low[v]);
else {
    redfs(v);
    low[u]=min(low[u],low[v]);
}
}
if (low[u]==num[u]){
    scc++;
    while (!t.empty()&&t.top()!=u){
    num[t.top()]=-1;
    t.pop();
    }
    num[u]=-1;
    t.pop();
}
}
void solve(){
    int n;
    cin>>n;
    for1(i,1,n){
    a[i].clear();
    g[i].clear();
    }
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    for1(i,0,17)for1(j,1,n)st[j][i]=0;
    dfs(1,0);
    int m;
    cin>>m;
    for1(i,1,m){
    low[i]=num[i]=0;
    cin>>b[i].fi>>b[i].se;
    }
    for1(i,1,m){
    for1(j,1,m){
    if (i==j)continue;
    if (onpath(b[i].fi,b[i].se,b[j].fi)){
    g[j].pb(i);
    //cout<<j<<" "<<i<<'\n';
    }
    if (onpath(b[i].fi,b[i].se,b[j].se)){
    g[i].pb(j);
    //cout<<i<<" "<<j<<'\n';
    }
    }
    }
    scc=tme=0;
    for1(i,1,m)if (!num[i])redfs(i);
    //cout<<low[1]<<" "<<num[1]<<" "<<low[2]<<" "<<num[2];
    if (scc==m)cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int t;
    cin>>t;
    while (t--)solve();
}

Compilation message

jail.cpp: In function 'void dfs(int, int)':
jail.cpp:27:21: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 | for1(i,1,17)st[v][i]=st[st[v][i-1]][i-1];
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
jail.cpp:7:34: note: within this loop
    7 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
   27 | for1(i,1,17)st[v][i]=st[st[v][i-1]][i-1];
      |      ~~~~~~                       
jail.cpp:27:1: note: in expansion of macro 'for1'
   27 | for1(i,1,17)st[v][i]=st[st[v][i-1]][i-1];
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 11 ms 10452 KB Output is correct
5 Correct 21 ms 10844 KB Output is correct
6 Correct 3 ms 10076 KB Output is correct
7 Correct 3 ms 10072 KB Output is correct
8 Correct 51 ms 10108 KB Output is correct
9 Correct 1695 ms 16088 KB Output is correct
10 Correct 133 ms 32112 KB Output is correct
11 Correct 19 ms 10072 KB Output is correct
12 Correct 551 ms 11156 KB Output is correct
13 Execution timed out 5017 ms 31576 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10104 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Incorrect 3 ms 10076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10104 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Incorrect 3 ms 10076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10104 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Incorrect 3 ms 10076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10104 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Incorrect 3 ms 10076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 3 ms 10092 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 2 ms 10076 KB Output is correct
5 Correct 19 ms 10208 KB Output is correct
6 Correct 2 ms 10076 KB Output is correct
7 Incorrect 2 ms 9900 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 11 ms 10452 KB Output is correct
5 Correct 21 ms 10844 KB Output is correct
6 Correct 3 ms 10076 KB Output is correct
7 Correct 3 ms 10072 KB Output is correct
8 Correct 51 ms 10108 KB Output is correct
9 Correct 1695 ms 16088 KB Output is correct
10 Correct 133 ms 32112 KB Output is correct
11 Correct 19 ms 10072 KB Output is correct
12 Correct 551 ms 11156 KB Output is correct
13 Execution timed out 5017 ms 31576 KB Time limit exceeded
14 Halted 0 ms 0 KB -