Submission #602637

#	Time	Username	Problem	Language	Result	Execution time	Memory
602637		gagik_2007	Jail (JOI22_jail)	C++17	5 / 100	181 ms	11984 KiB

jail

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
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];
        }
    }
}

//v-n u-i papn e te voch
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];
        }
    }
    return up[u][0];
}

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

int main() {
    cin >> ttt;
    while (ttt--) {
        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 <= 2) {
            if (m == 1)cout << "Yes" << endl;
            else {
                dfs(1, 1);
                calc();
                if (votitak(s[1], f[1], s[2]) &&
                    (votitak(s[2], f[2], f[1]) || votitak(s[2], f[2], s[1]))) {
                    cout << "No" << endl;
                }
                else if (votitak(s[1], f[1], f[2]) &&
                    (votitak(s[2], f[2], f[1]) || votitak(s[2], f[2], s[1]))) {
                    cout << "No" << endl;
                }
                else cout << "Yes" << endl;
                timer = 1;
                fill(tin, tin + 120007, 0);
                fill(tout, tout + 120007, 0);
                for (int i = 1; i <= n; i++) {
                    g[i].clear();
                }
            }
        }
    }
}

Compilation message (stderr)

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

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