Submission #641440

#	Time	Username	Problem	Language	Result	Execution time	Memory
641440		Alexandruabcde	Colors (RMI18_colors)	C++14	100 / 100	798 ms	70028 KiB

colors

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;
constexpr int NMAX = 15e4 + 5;

vector <int> G[NMAX];

int N, M;

int A[NMAX];
int B[NMAX];

vector <int> Add[NMAX];
vector <int> Remove[NMAX];

class Dynamic_Conectivity {
private:
    vector <int> arb[4*NMAX];
    int arb_size;

    bool Unlocked[NMAX];
    bool Good[NMAX];
    int Dad[NMAX];
    int Sz[NMAX];
    vector <PII> DSU;

    int Reprezentant (int Node) {
        if (Node == Dad[Node]) return Node;

        return Reprezentant(Dad[Node]);
    }

    void Unite (int x, int y) {
        x = Reprezentant(x);
        y = Reprezentant(y);

        if (x == y) return;

        if (Sz[x] <= Sz[y]) {
            Dad[x] = y;
            Sz[y] += Sz[x];

            DSU.push_back({x, y});
        }
        else {
            Dad[y] = x;
            Sz[x] += Sz[y];

            DSU.push_back({y, x});
        }
    }

    void Delete_Last () {
        if (DSU.empty()) return;

        PII last = DSU.back();
        DSU.pop_back();

        Dad[last.first] = last.first;
        Sz[last.second] -= Sz[last.first];
    }

    void Add_Point (int x) {
        Unlocked[x] = true;

        for (auto it : G[x]) {
            if (!Unlocked[it]) continue;

            Unite(x, it);
        }
    }

    void Init_Tree (int nod, int a, int b) {
        arb[nod].clear();

        if (a == b) return;

        int mij = (a + b) / 2;

        Init_Tree(2*nod, a, mij);
        Init_Tree(2*nod + 1, mij+1, b);
    }

    void Update (int nod, int a, int b, int ua, int ub, int who) {
        if (ua <= a && b <= ub) {
            arb[nod].push_back(who);
            return;
        }

        int mij = (a + b) / 2;

        if (ua <= mij) Update(2*nod, a, mij, ua, ub, who);
        if (mij < ub) Update(2*nod+1, mij+1, b, ua, ub, who);
    }

    bool Query (int nod, int a, int b) {
        int aux_sz = DSU.size();
        for (auto it : arb[nod])
            Add_Point(it);

        bool ans = true;
        if (a == b) {
            for (auto it : Add[a])
                Good[Reprezentant(it)] = true;

            for (auto it : Remove[a])
                ans &= Good[Reprezentant(it)];

            for (auto it : Add[a])
                Good[Reprezentant(it)] = false;

            while (DSU.size() > aux_sz)
                Delete_Last();

            for (auto it : arb[nod])
                Unlocked[it] = false;
            return ans;
        }

        int mij = (a + b) / 2;

        ans = (Query(2*nod, a, mij)&Query(2*nod+1, mij+1, b));

        while (DSU.size() > aux_sz)
            Delete_Last();

        for (auto it : arb[nod])
            Unlocked[it] = false;

        return ans;
    }

public:

    void Initialize (int N) {
        arb_size = N;
        Init_Tree(1, 1, N);

        for (int i = 1; i <= N; ++ i ) {
            Unlocked[i] = false;
            Dad[i] = i;
            Sz[i] = 1;
        }

        DSU.clear();
    }

    void Add_Interval (int st, int dr, int who) {
        Update(1, 1, arb_size, st, dr, who);
    }

    bool Check () {
        return Query(1, 1, arb_size);
    }
};

Dynamic_Conectivity DCC;

void Read () {
    cin >> N >> M;

    for (int i = 1; i <= N; ++ i )
        cin >> A[i];

    for (int i = 1; i <= N; ++ i )
        cin >> B[i];

    for (int i = 1; i <= M; ++ i ) {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }
}

bool ans;

void Solve () {
    DCC.Initialize(N);
    ans = true;

    for (int i = 1; i <= N; ++ i ) {
        Add[A[i]].push_back(i);
        Remove[B[i]].push_back(i);

        if (B[i] > A[i]) ans = false;

        DCC.Add_Interval(B[i], A[i], i);
    }

    ans &= DCC.Check();

    cout << ans << '\n';
}

void Reset () {
    for (int i = 1; i <= N; ++ i ) {
        Add[i].clear();
        Remove[i].clear();

        G[i].clear();
    }
}

void Do_Testcase () {
    Read();

    Solve();

    Reset();
}

int main () {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    for (; T; -- T ) {
        Do_Testcase();
    }
    return 0;
}

Compilation message (stderr)

colors.cpp: In member function 'bool Dynamic_Conectivity::Query(int, int, int)':
colors.cpp:114:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |             while (DSU.size() > aux_sz)
      |                    ~~~~~~~~~~~^~~~~~~~
colors.cpp:126:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  126 |         while (DSU.size() > aux_sz)
      |                ~~~~~~~~~~~^~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22