Submission #621432

#	Time	Username	Problem	Language	Result	Execution time	Memory
621432		MDario	Jail (JOI22_jail)	C++11	100 / 100	1695 ms	444972 KiB

jail

#include<bits/stdc++.h>
#pragma GCC optimization("Ofast")
#pragma GCC target("avx2")
#pragma once
using namespace std;
typedef long long ll;
#define F first
#define S second
const ll mod=1e9+7;
int q, n, m, level[120001], p[120001][20], c[20];
string s;
vector<int> v[120001], cycle[10000001];
bitset<10000001> b, b1;
void dfs1(int xf, int axf){
    p[xf][0]=axf;
    level[xf]=level[axf]+1;
    for(int i=1; i<20; i++){
        p[xf][i]=p[p[xf][i-1]][i-1];
        cycle[xf*40+m+20+i].push_back(xf*40+m+20+i-1);
        cycle[xf*40+m+20+i].push_back(p[xf][i-1]*40+m+20+i-1);
        cycle[xf*40+m+i-1].push_back(xf*40+m+i);
        cycle[p[xf][i-1]*40+m+i-1].push_back(xf*40+m+i);
    }
    for(auto i : v[xf]){
        if(i!=axf){
            dfs1(i, xf);
        }
    }
    return;
}
void update1(int xf, int yf, int zf){
    if(level[xf]>level[yf])swap(xf, yf);
    for(int i=19; i>=0; i--){
        if(level[yf]-(1<<i)>=level[xf]){
            cycle[zf].push_back(yf*40+m+20+i);
            yf=p[yf][i];
        }
    }
    if(xf!=yf){
        for(int i=19; i>=0; i--){
            if(p[yf][i]!=p[xf][i]){
                cycle[zf].push_back(yf*40+m+20+i);
                yf=p[yf][i];
                cycle[zf].push_back(xf*40+m+20+i);
                xf=p[xf][i];
            }
        }
        cycle[zf].push_back(yf*40+m+20+0);
        yf=p[yf][0];
        cycle[zf].push_back(xf*40+m+20+0);
        xf=p[xf][0];
    }
    cycle[zf].push_back(yf*40+m+20);
    return;
}
void update2(int xf, int yf, int zf){
    if(level[xf]>level[yf])swap(xf, yf);
    for(int i=19; i>=0; i--){
        if(level[yf]-(1<<i)>=level[xf]){
            cycle[yf*40+m+i].push_back(zf);
            yf=p[yf][i];
        }
    }
    if(xf!=yf){
        for(int i=19; i>=0; i--){
            if(p[yf][i]!=p[xf][i]){
                cycle[yf*40+m+i].push_back(zf);
                yf=p[yf][i];
                cycle[xf*40+m+i].push_back(zf);
                xf=p[xf][i];
            }
        }
        cycle[yf*40+m+0].push_back(zf);
        yf=p[yf][0];
        cycle[xf*40+m+0].push_back(zf);
        xf=p[xf][0];
    }
    cycle[yf*40+m].push_back(zf);
    return;
}
void update(int xf, int yf, int zf){
    if(xf==yf)return;
    if(level[xf]>level[yf]){
        update2(p[xf][0], yf, zf);
        c[5]=xf;
        for(int i=19; i>=0; i--){
            if(level[xf]-(1<<i)>level[yf]){
                xf=p[xf][i];
            }
        }
        if(p[xf][0]==yf)update1(xf, c[5], zf);
        else update1(p[yf][0], c[5], zf);
    }
    else{
        update1(xf, p[yf][0], zf);
        c[5]=yf;
        for(int i=19; i>=0; i--){
            if(level[yf]-(1<<i)>level[xf]){
                yf=p[yf][i];
            }
        }
        if(p[yf][0]==xf)update2(yf, c[5], zf);
        else update2(p[xf][0], c[5], zf);
    }
    return;
}
bool dfs2(int xf){
    if(b1[xf])return 1;
    if(b[xf])return 0;
    b[xf]=1;
    b1[xf]=1;
    for(auto i : cycle[xf]){
        if(dfs2(i))return 1;
    }
    b1[xf]=0;
    return 0;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> q;
    while(q--){
        cin >> n;
        for(int i=1; i<=n; i++)v[i].clear();
        for(int i=1; i<n; i++){
            cin >> c[0] >> c[1];
            v[c[0]].push_back(c[1]);
            v[c[1]].push_back(c[0]);
        }
        cin >> m;
        for(int i=0; i<=(n+1)*40+m; i++){
            b[i]=0;
            b1[i]=0;
            cycle[i].clear();
        }
        level[1]=0;
        dfs1(1, 1);
        for(int i=0; i<m; i++){
            cin >> c[0] >> c[1];
            update(c[0], c[1], i);
            cycle[c[1]*40+m+20].push_back(i);
            cycle[i].push_back(c[0]*40+m);
        }
        c[0]=0;
        for(int i=0; i<m; i++){
            if(dfs2(i)){
                c[0]=1;
                break;
            }
        }
        if(c[0])cout << "No\n";
        else cout << "Yes\n";
    }
    return 0;
}

Compilation message (stderr)

jail.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("Ofast")
      | 
jail.cpp:4:9: warning: #pragma once in main file
    4 | #pragma once
      |         ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23