Submission #609641

#	Time	Username	Problem	Language	Result	Execution time	Memory
609641		gagik_2007	Jail (JOI22_jail)	C++17	66 / 100	736 ms	25072 KiB

jail

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

string findSum(string str1, string str2)
{
    if (str1.length() > str2.length())
        swap(str1, str2);
    string str = "";
    ll n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (ll i = 0; i < n1; i++)
    {
        ll sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    for (ll i = n1; i < n2; i++)
    {
        ll sum = ((str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    if (carry)
        str.push_back(carry + '0');
    reverse(str.begin(), str.end());
    return str;
}
bool isSmaller(string str1, string str2)
{
    ll n1 = str1.length(), n2 = str2.length();
    if (n1 < n2)
        return true;
    if (n2 < n1)
        return false;
    for (ll i = 0; i < n1; i++)
        if (str1[i] < str2[i])
            return true;
        else if (str1[i] > str2[i])
            return false;
    return false;
}
string findDiff(string str1, string str2)
{
    if (isSmaller(str1, str2))
        swap(str1, str2);
    string str = "";
    ll n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (ll i = 0; i < n2; i++) {
        ll sub
            = ((str1[i] - '0') - (str2[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    for (ll i = n2; i < n1; i++) {
        ll sub = ((str1[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    reverse(str.begin(), str.end());
    return str;
}

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;
vector<int>g[120007];
ll s[120007];
ll f[120007];
queue<int>q;

struct Point {
    int ind, val, tp;
    Point(int i, int vl, int tip) {
        ind = i;
        val = vl;
        tp = tip;
    }
    bool operator<(Point other)const {
        if (val < other.val)return true;
        else if (val > other.val)return false;
        else return tp < other.tp;
    }
};

vector<Point>d;
int tin[120007];
int tout[120007];
int timer = 0;
int up[120007][20];
int lg;

void dfs(int v, int par) {
    tin[v] = timer++;
    up[v][0] = par;
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (to != par) {
            dfs(to, v);
        }
    }
    tout[v] = timer++;
}

void calc() {
    for (int i = 1; i <= lg; i++) {
        for (int v = 1; v <= n; v++) {
            up[v][i] = up[up[v][i - 1]][i - 1];
        }
    }
}

bool pap(int v, int u) {
    return tin[v]<=tin[u] && tout[v]>=tout[u];
}

int lca(int v, int u) {
    if (pap(v, u)) {
        return v;
    }
    if (pap(u, v)) {
        return u;
    }
    for (int i = lg; i >= 0; i--) {
        if (!pap(up[u][i], v)) {
            u = up[u][i];
        }
    }
    //cout << "lca of " << v << " and " << u << " is: " << up[u][0] << endl;
    return up[u][0];
}

bool votitak(int v, int u, int c) {
    return pap(lca(v, u), c) && (pap(c, u) || pap(c, v));
}

vector<int> champa(int v, int u){
    int papa = lca(v,u);
    vector<int>ans;
    while(v!=papa){
        ans.push_back(v);
        v=up[v][0];
    }
    while(u!=papa){
        ans.push_back(u);
        u=up[u][0];
    }
    ans.push_back(papa);
    return ans;
}

vector<int>g2[120007];
int color[120007];
int prc[120007];
int skz[120007];

bool is_cyclic(int v){
    color[v]=1;
    bool ans=false;
    for(int i=0;i<g2[v].size();i++){
        int to=g2[v][i];
        if(color[to]==1)ans=true;
        if(color[to]==0){
            if(is_cyclic(to)){
                ans=true;
            }
        }
    }
    color[v]=2;
    return ans;
}

void sax_jnjxel(){
    timer = 0;
    fill(tin, tin + 120007, 0);
    fill(tout, tout + 120007, 0);
    fill(color,color+120007,0);
    fill(prc,prc+120007,0);
    fill(skz,skz+120007,0);
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        g2[i].clear();
    }
}

void solve(){
    cin >> n;
    lg = ceil(log2(n));
    bool ent1 = true;
    for (int i = 0; i < n - 1; i++) {
        ll x, y;
        cin >> x >> y;
        if (x != i + 1 || y != i + 2) {
            ent1 = false;
        }
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> s[i] >> f[i];
    }
    //ent1 = false;
    if (ent1) {
        for (int i = 1; i <= m; i++) {
            Point x(i, s[i], 1), y(i, f[i], -1);
            d.push_back(x);
            d.push_back(y);
        }
        sort(d.begin(), d.end());
        bool aj = (d[0].tp == 1);
        bool ok = true;
        for (auto x : d) {
            //cout << x.ind << " " << x.tp << "  ";
            if (aj) {
                if (x.tp == 1) {
                    q.push(x.ind);
                }
                else {
                    if (q.empty()) {
                        aj = false;
                        q.push(x.ind);
                    }
                    else {
                        if (x.ind != q.front()) {
                            ok = false;
                            break;
                        }
                        else {
                            q.pop();
                        }
                    }
                }
            }
            else {
                if (x.tp == -1) {
                    q.push(x.ind);
                }
                else {
                    if (q.empty()) {
                        aj = true;
                        q.push(x.ind);
                    }
                    else {
                        if (x.ind != q.front()) {
                            ok = false;
                            break;
                        }
                        else {
                            q.pop();
                        }
                    }
                }
            }
        }
        cout << (ok ? "Yes" : "No") << endl;
        while (!q.empty()) {
            q.pop();
        }
        d.clear();
        for (int i = 1; i <= n; i++) {
            g[i].clear();
        }
    }
    else if(m<=500){
        dfs(1, 1);
        calc();
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                if(j!=i){
                    bool skizb = votitak(f[i],s[i],f[j]);
                    bool verj = votitak(f[i],s[i],s[j]);
                    if(skizb&&verj){
                        //cout<<i<<" "<<j<<endl;
                        cout<<"No"<<endl;
                        sax_jnjxel();
                        return;
                    }
                    if(skizb){
                        g2[i].push_back(j);
                    }
                    else if(verj){
                        g2[j].push_back(i);
                    }
                }
            }
        }
        bool res=false;
        for(int i=1;i<=m;i++){
            if(color[i]==0){
                if(is_cyclic(i)){
                    res=true;
                    break;
                }
            }
        }
        if(!res){
            cout<<"Yes"<<endl;
        }
        else cout<<"No"<<endl;
        sax_jnjxel();
    }
    else{
        dfs(1, 1);
        calc();
        for(int i=1;i<=m;i++){
            prc[s[i]]=i;
            skz[f[i]]=i;
        }
        for(int i=1;i<=m;i++){
            vector<int>c=champa(f[i],s[i]);
            for(auto x:c){
                if(prc[x]!=0&&prc[x]!=i){
                    g2[prc[x]].push_back(i);
                }
                if(skz[x]!=0&&skz[x]!=i){
                    g2[x].push_back(skz[x]);
                }
            }
        }
        bool res=false;
        for(int i=1;i<=m;i++){
            if(color[i]==0){
                if(is_cyclic(i)){
                    res=true;
                    break;
                }
            }
        }
        if(!res){
            cout<<"Yes"<<endl;
        }
        else cout<<"No"<<endl;
        sax_jnjxel();
    }
}

int main() {
    cin >> ttt;
    while (ttt--) {
        solve();
    }
}

/*
4
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 3
2 7
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 3
7 2
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 7
3 2
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 7
3 4
*/

Compilation message (stderr)

jail.cpp: In function 'void dfs(int, int)':
jail.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < g[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
jail.cpp: In function 'bool is_cyclic(int)':
jail.cpp:185:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for(int i=0;i<g2[v].size();i++){
      |                 ~^~~~~~~~~~~~~

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