1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m, k, h, ans = 0;
        cin >> n >> m >> k >> h;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            int dif = abs(tmp - h);
            if (dif == 0 || dif % k) continue;
            if (dif / k < m) ans++;
        }
        cout << ans << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data1(n), data2(n);
        for (int i = 0; i < n; ++i) cin >> data1[i];
        for (int i = 0; i < n; ++i) data2[i] = data1[i];
        sort(data2.begin(), data2.end());
        bool check = false;
        for (int i = 0; i < n; ++i) if (data1[i] % 2 != data2[i] % 2) check = true;
        cout << (check ? "NO" : "YES") << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        vector<int> data(n);
        for (int i = 0; i < n; ++i) cin >> data[i];
        if (data.front() == data.back()) {
            int cnt = 0;
            for (int i = 0; i < n; ++i) cnt += data[i] == data.front();
            cout << (cnt >= k ? "YES" : "NO") << endl;
        } else {
            int cnt1 = 0, cnt2 = 0;
            for (int i = 0; i < n; ++i)
                if (cnt1 >= k) cnt2 += data[i] == data.back();
                else cnt1 += data[i] == data.front();
            cout << (cnt1 >= k && cnt2 >= k ? "YES" : "NO") << endl;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#define int long long
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        set<int> st;
        for (int i = 0; i < n; ++i) st.insert(i + 1);
        int last = 0, out = -1;
        for (int i = 0; i < n - 1; ++i) {
            int tmp;
            cin >> tmp;
            auto iter = st.find(tmp - last);
            if (iter == st.end()) out = tmp - last;
            else st.erase(iter);
            last = tmp;
        }
        if (st.size() == 1 && out == -1) {
            cout << "YES" << endl;
            continue;
        }
        if (st.size() != 2) {
            cout << "NO" << endl;
            continue;
        }
        int a, b;
        a = *st.begin();
        b = *(++st.begin());
        cout << (a + b == out ? "YES" : "NO") << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#define int long long
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        vector<int> cost(n + 1);
        for (int i = 1; i <= n; ++i) cin >> cost[i];
        for (int i = 0; i < k; ++i) {
            int tmp;
            cin >> tmp;
            cost[tmp] = 0;
        }
        vector<vector<int>> from(n + 1);
        vector<vector<int>> to(n + 1);
        vector<int> in(n + 1, 0);
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            int cnt;
            cin >> cnt;
            if (cnt == 0) q.push(i);
            for (int j = 0; j < cnt; ++j) {
                int tmp;
                cin >> tmp;
                from[i].push_back(tmp);
                to[tmp].push_back(i);
                in[i]++;
            }
        }
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            if (!from[cur].empty()) {
                int c = 0;
                for (auto &item: from[cur]) c += cost[item];
                cost[cur] = min(cost[cur], c);
            }
            for (auto &item : to[cur])
                if (--in[item] == 0) q.push(item);
        }
        for (int i = 1; i <= n; ++i) cout << cost[i] << " \n"[i == n];
    }
}

1
2
3
4

struct node {
    int zero = -1, one = -1, cnt = 0;
    vector<int> index;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        struct node {
            int zero = -1, one = -1, cnt = 0;
            vector<int> index;
        };
        int n, k;
        cin >> n >> k;
        vector<node> tree(n * 40);
        int rNode = 1, root = 0;
        auto newNode = [&]() {
            return rNode++;
        };
        auto add = [&](int x, int index) {
            tree[root].cnt++;
            int cur = root;
            for (int i = k - 1; i >= 0; --i) {
                if (x & (1 << i)) {
                    cur = tree[cur].one == -1 ? tree[cur].one = newNode() : tree[cur].one;
                    tree[cur].cnt++;
                } else {
                    cur = tree[cur].zero == -1 ? tree[cur].zero = newNode() : tree[cur].zero;
                    tree[cur].cnt++;
                }
            }
            tree[cur].index.push_back(index);
        };
        auto find = [&](int cur, int &x, int deep) {
            while (cur != -1) {
                if (tree[cur].zero == -1 && tree[cur].one == -1) return tree[cur].index[0];
                if (tree[cur].zero == -1) {
                    x |= 1 << deep;
                    cur = tree[cur].one;
                } else cur = tree[cur].zero;
                deep--;
            }
            return -1;
        };
        int res = INT_MIN, resX, l, r;
        function<void(int, int x, int)> dfs = [&](int cur, int x, int deep) {
            if (tree[cur].zero == -1 && tree[cur].one == -1) {
                assert(tree[cur].cnt >= 2 && tree[cur].index.size() >= 2);
                res = (1 << k) - 1;
                l = tree[cur].index[0];
                r = tree[cur].index[1];
                resX = x;
                return;
            }
            if (tree[cur].zero == -1) dfs(tree[cur].one, x, deep - 1);
            else if (tree[cur].one == -1) dfs(tree[cur].zero, x | (1 << deep), deep - 1);
            else {
                if (tree[tree[cur].zero].cnt >= 2) dfs(tree[cur].zero, x | (1 << deep), deep - 1);
                if (tree[tree[cur].one].cnt >= 2) dfs(tree[cur].one, x, deep - 1);
                if (tree[tree[cur].zero].cnt == 1 && tree[tree[cur].one].cnt == 1) {
                    int lv = 0, rv = 1 << deep;
                    int li = find(tree[cur].zero, lv, deep - 1);
                    int ri = find(tree[cur].one, rv, deep - 1);
                    int tmp = 0;
                    for (int i = k - 1; i > deep; --i) tmp |= 1 << i;
                    for (int i = deep; i >= 0; --i) if ((lv & (1 << i)) == (rv & (1 << i))) {
                        tmp |= 1 << i;
                        x |= (lv & (1 << i)) ? 0 : 1 << i;
                    }
                    if (tmp > res) {
                        l = li;
                        r = ri;
                        resX = x;
                        res = tmp;
                    }
                }
            }
        };
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            add(tmp, i + 1);
        }
        dfs(0, 0, k - 1);
        cout << l << ' ' << r << ' ' << resX << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

void solve() {
    struct node {
        int v, n;
    };
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> h(n + 1);
        vector<node> edge(m);
        vector<int> head(n + 1, -1);
        for (int i = 1; i <= n; ++i) cin >> h[i].first;
        for (int i = 1; i <= n; ++i) h[i].second = i;
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            if (h[u].first > h[v].first) {
                edge[i] = {v, head[u]};
                head[u] = i;
            } else {
                edge[i] = {u, head[v]};
                head[v] = i;
            }
        }
        int q;
        cin >> q;
        struct query {
            int u, v, e, i;
        };
        vector<query> ql(q);
        vector<bool> ans(q);
        for (int i = 0; i < q; ++i) cin >> ql[i].u >> ql[i].v >> ql[i].e;
        for (int i = 0; i < q; ++i) ql[i].e += h[ql[i].u].first;
        for (int i = 0; i < q; ++i) ql[i].i = i;
        sort(h.begin() + 1, h.end());
        sort(ql.begin(), ql.end(), [&](const query &a, const query &b) { return a.e < b.e; });
        vector<int> fa(n + 1);
        for (int i = 0; i < fa.size(); ++i) fa[i] = i;
        function<int(int)> find = [&](int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); };
        auto join = [&](int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return;
            fa[rx] = ry;
        };
        int last = 0, qPtr = 0;
        for (int i = 1; i <= n; ++i) {
            if (last != h[i].first) {
                while (qPtr < q && ql[qPtr].e < h[i].first) {
                    auto &que = ql[qPtr];
                    int ru = find(que.u), rv = find(que.v);
                    ans[que.i] = ru == rv;
                    qPtr++;
                }
            }
            last = h[i].first;
            for (int j = head[h[i].second]; j != -1; j = edge[j].n) join(h[i].second, edge[j].v);
        }
        while (qPtr < q) {
            auto &que = ql[qPtr];
            int ru = find(que.u), rv = find(que.v);
            ans[que.i] = ru == rv && ql[qPtr].e >= last;
            qPtr++;
        }
        for (auto item: ans) cout << (item ? "YES" : "NO") << endl;
        cout << endl;
    }
}