Доп контест Ксюше

// 1 задача
#include <iostream>
#include <vector>

using namespace std;

class Task {
    vector<int> parent;
    vector<int> my_rank;
    vector<vector<int>> values;
public:

    Task(int n) {
        parent.resize(n);
        my_rank.resize(n);
        values.resize(n);
    }

    void make_set(int x) {
        parent[x] = x;
        my_rank[x] = 0;
        values[x].push_back(x + 1);
    }

    int find_set(int x) {
        if (x == parent[x])
            return x;
        return find_set(parent[x]);
    }

    void union_sets(int first_cage, int second_cage) {
        first_cage = find_set(first_cage);
        second_cage = find_set(second_cage);
        if (first_cage != second_cage) {
            if (my_rank[first_cage] < my_rank[second_cage])
                swap(first_cage, second_cage);

            // доабвляем котят в большую клетку
            values[first_cage].insert(values[first_cage].end(), values[second_cage].begin(), values[second_cage].end());

            parent[second_cage] = first_cage;
            if (my_rank[first_cage] == my_rank[second_cage])
                my_rank[first_cage]++;

        }
    }

    void print_answer() {
        for (int i : values[find_set(0)]) {
            cout << i;
            cout << ' ';
        }
    }
};

int main() {
    int n;
    cin >> n;
    Task t(n);
    for (int i = 0; i < n; i++)
        t.make_set(i);
    for (int i = 0; i < n; i++) {
        int from, to;
        cin >> from >> to;
        from -= 1;
        to -= 1;
        t.union_sets(from, to);
    }
    t.print_answer();

}

// 2 задача

#include <iostream>
#include <vector>

using namespace std;

class Task {
    vector<int> parent;
    vector<int> my_rank;
    vector<string> query_type;
    vector<int> query_a;
    vector<int> query_b;
    vector<string> answers;
public:

    Task(int n) {
        parent.resize(n);
        my_rank.resize(n);
        for (int i = 0; i < n; i++)
            make_set(i);
    }

    void make_set(int x) {
        parent[x] = x;
        my_rank[x] = 0;
    }

    int find_set(int x) {
        if (x == parent[x])
            return x;
        return find_set(parent[x]);
    }

    void union_sets(int first_cage, int second_cage) {
        first_cage = find_set(first_cage);
        second_cage = find_set(second_cage);
        if (first_cage != second_cage) {
            if (my_rank[first_cage] < my_rank[second_cage])
                swap(first_cage, second_cage);

            parent[second_cage] = first_cage;
            if (my_rank[first_cage] == my_rank[second_cage])
                my_rank[first_cage]++;

        }
    }

    void read_graph(int m) {
        int kek;
        for (int i = 0; i < m; i++)
            cin >> kek;
        for (int i = 0; i < m; i++)
            cin >> kek;
    }

    void read_queries(int k){
        query_type.resize(k);
        query_a.resize(k);
        query_b.resize(k);
        for (int i = 0; i < k; i++){
            cin >> query_type[i] >> query_a[i] >> query_b[i];
            query_a[i]--;
            query_b[i]--;
        }
    }

    void process_queries(int k){
        for (int i = k - 1; i >= 0; i--){
            if (query_type[i] == "cut"){
                union_sets(query_a[i], query_b[i]);
            } else {
                if (find_set(query_a[i]) == find_set(query_b[i]))
                    answers.emplace_back("YES");
                else
                    answers.emplace_back("NO");
            }
        }
    }

    void print_answers(){
        for (int i = 0; i < answers.size(); i++)
            cout << answers[answers.size() - 1 - i] << endl;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    Task t(n);
    t.read_graph(m);
    t.read_queries(k);
    t.process_queries(k);
    t.print_answers();
}

// 3 задача

#include <iostream>
#include <vector>

using namespace std;

class Task {
    int n, m;
    vector<int> used;
    vector<vector<int>> th;
    vector<int> order;

    void end_task(){
        cout << "No";
        exit(0);
    }

    void dfs(int v, int p) {
        used[v] = 1;
        for (auto &i: th[v]) {
            if (used[i] == 1) {
                end_task();
            }
            if (used[i] == 0) {
                dfs(i, v);
            }
        }
        used[v] = 2;
        order.push_back(v);
    }
public:

    Task(int _n, int _m){
        n = _n;
        m = _m;
        used.resize(n);
        th.resize(n);
        // order.resize(n);

    }

    void read_graph(){
        for (int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            a--; b--;
            th[a].push_back(b);
        }
    }


    void solve(){
        for (int i = 0; i < n; i++){
            if (!used[i])
                dfs(i, -1);
        }
        cout << "Yes" << endl;
        for (int i = 0; i < n; i++){
            cout << order[n - 1 - i] + 1 << " ";
        }
    }

};
int main() {
    int n, m;
    cin >> n >> m;

    Task t(n, m);
    t.read_graph();
    t.solve();

    return 0;
}

// 4 задача
#include <iostream>
#include <vector>

using namespace std;

class Task {
    vector<int> parent;
    vector<int> my_rank;
    int c = 0;
public:

    Task(int n) {
        parent.resize(n);
        my_rank.resize(n);
        for (int i = 0; i < n; i++)
            make_set(i);
        c = n;
    }

    void make_set(int x) {
        parent[x] = x;
        my_rank[x] = 0;
    }

    int find_set(int x) {
        if (x == parent[x])
            return x;
        return find_set(parent[x]);
    }

    void union_sets(int first_cage, int second_cage) {
        first_cage = find_set(first_cage);
        second_cage = find_set(second_cage);
        if (first_cage != second_cage) {
            if (my_rank[first_cage] < my_rank[second_cage])
                swap(first_cage, second_cage);

            parent[second_cage] = first_cage;
            if (my_rank[first_cage] == my_rank[second_cage])
                my_rank[first_cage]++;
            c--;
        }
    }
    int get_c(){
        return c;
    }
};

int main() {
    int n;
    cin >> n;

    Task t(n);
    for (int i = 0; i < n; i++){
        int key;
        cin >> key;
        key--;
        t.union_sets(i, key);
    }

    cout << t.get_c();

}

// 7 задача
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

struct Edge {
    int to;
    int departing_time;
    int arrival_time;
};

class Task {

    int n;

    vector<int> used;

    vector<vector<Edge>> th;

    vector<int> th_time;

public:

    Task(int _n) {
        n = _n;
        th.resize(n);
        used.resize(n);
        th_time.resize(n, INT_MAX);
    }

    void read_graph(int m) {
        for (int i = 0; i < m; i++) {
            int k;
            cin >> k;

            int from, to, from_t, to_t;
            for (int j = 0; j < k; j++) {
                cin >> to >> to_t;
                to-=1;
                if (j > 0) {
                    th[from].push_back(Edge{to, from_t, to_t});
                }
                from = to;
                from_t = to_t;
            }
        }
    }

    void dijkstra() {
        for (;;) {
            int min_v = -1, min_dist = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (!used[i] && th_time[i] < min_dist) {
                    min_v = i;
                    min_dist = th_time[i];
                }
            }
            if (min_v == -1)
                return;
            used[min_v] = true;
            for (auto &i: th[min_v]) {
                if (i.departing_time >= th_time[min_v] && i.arrival_time < th_time[i.to])
                    th_time[i.to] = i.arrival_time;
            }
        }
    }

    void solve(int start) {
        th_time[start] = 0;
        dijkstra();
    }

    void print_result(int finish) {
        if (th_time[finish] != INT_MAX)
            cout << th_time[finish];
        else
            cout << "-1";
    }
};

int main() {
    int n, m, finish;
    cin >> n >> finish >> m;

    Task t(n);
    t.read_graph(m);
    t.solve(0);
    t.print_result(finish - 1);


    return 0;
}

// 8 задача

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

struct Edge {
    int to;
    int departing_time;
    int arrival_time;
};

class Task {

    int n;

    vector<int> used;

    vector<vector<Edge>> th;

    vector<int> th_time;

public:

    Task(int _n) {
        n = _n;
        th.resize(n);
        used.resize(n);
        th_time.resize(n, INT_MAX);
    }

    void read_graph(int m) {
        for (int i = 0; i < m; i++) {
            int from, from_t, to, to_t;
            cin >> from >> from_t >> to >> to_t;
            th[from - 1].push_back(Edge{to - 1, from_t, to_t});
        }
    }

    void dijkstra() {
        for (;;) {
            int min_v = -1, min_dist = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (!used[i] && th_time[i] < min_dist) {
                    min_v = i;
                    min_dist = th_time[i];
                }
            }
            if (min_v == -1)
                return;
            used[min_v] = true;
            for (auto &i: th[min_v]) {
                if (i.departing_time >= th_time[min_v] && i.arrival_time < th_time[i.to])
                    th_time[i.to] = i.arrival_time;
            }
        }
    }

    void solve(int start) {
        th_time[start] = 0;
        dijkstra();
    }

    void print_result(int finish) {
        if (th_time[finish] != INT_MAX)
            cout << th_time[finish];
        else
            cout << "-1";
    }
};

int main() {
    int n, m, finish, start;
    cin >> n >> start >> finish >> m;

    Task t(n);
    t.read_graph(m);
    t.solve(start - 1);
    t.print_result(finish - 1);


    return 0;
}