Submission #602583

#	Time	Username	Problem	Language	Result	Execution time	Memory
602583		gagik_2007	Jail (JOI22_jail)	C++17	5 / 100	159 ms	11956 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 main() {
    cin >> ttt;
    while (ttt--) {
        cin >> 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];
        }
        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();
            }
        }
    }
}

• 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