Submission #555378

#	Time	Username	Problem	Language	Result	Execution time	Memory
555378		Alexandruabcde	Bridges (APIO19_bridges)	C++14	100 / 100	2355 ms	77456 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;
constexpr int NMAX = 5e4 + 5;
constexpr int MMAX = 1e5 + 5;

struct Edge {
    int x, y;
    int weight;
};
Edge E[MMAX];

struct Query {
    int tip;
    int who, weight;
};
Query q[MMAX];

bool cmp_Edge (int a, int b) {
    return E[a].weight > E[b].weight;
}

bool cmp_Query (int a, int b) {
    return q[a].weight > q[b].weight;
}

int ans[MMAX];

int N, M, Q;

int Dad[NMAX];
int Size[NMAX];

void Reset () {
    for (int i = 1; i <= N; ++ i ) {
        Dad[i] = i;
        Size[i] = 1;
    }
}

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

    return Reprezentant(Dad[x]);
}

vector <PII> S;

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

    if (x == y) return;

    if (Size[x] > Size[y]) swap(x, y);

    Dad[x] = y;
    Size[y] += Size[x];
    S.push_back({x, y});
}

void Return (int sz) {
    while (S.size() > sz) {
        int x = S.back().first;
        int y = S.back().second;

        Dad[x] = x;
        Size[y] -= Size[x];
        S.pop_back();
    }
}

bool changed[MMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= M; ++ i )
        cin >> E[i].x >> E[i].y >> E[i].weight;

    cin >> Q;
    for (int i = 1; i <= Q; ++ i )
        cin >> q[i].tip >> q[i].who >> q[i].weight;
}

vector <int> ForcedUnion[1005];

void Solve () {
    int Batch = 1000;

    for (int st = 1; st <= Q; st += Batch) {
        Reset();
        int dr = min(st + Batch - 1, Q);

        vector <int> modif;
        vector <int> ask;
        vector <int> nemodif;

        for (int i = st; i <= dr; ++ i ) {
            if (q[i].tip == 1) {
                changed[q[i].who] = 1;
                modif.push_back(i);
            }
            else ask.push_back(i);
        }

        for (int i = 1; i <= M; ++ i )
            if (!changed[i]) nemodif.push_back(i);

        for (int i = st; i <= dr; ++ i ) {
            if (q[i].tip == 1) E[q[i].who].weight = q[i].weight;
            else {
                ForcedUnion[i-st+1].clear();

                for (auto chg : modif)
                    if (E[q[chg].who].weight >= q[i].weight) ForcedUnion[i-st+1].push_back(q[chg].who);
            }
        }

        sort(nemodif.begin(), nemodif.end(), cmp_Edge);
        sort(ask.begin(), ask.end(), cmp_Query);

        int ind = 0;
        for (auto itr : ask) {
            while (ind < nemodif.size() && E[nemodif[ind]].weight >= q[itr].weight) {
                Union(E[nemodif[ind]].x, E[nemodif[ind]].y);

                ++ ind;
            }

            int GoBack = S.size();

            for (auto index : ForcedUnion[itr - st + 1])
                Union(E[index].x, E[index].y);

            ans[itr] = Size[Reprezentant(q[itr].who)];

            Return(GoBack);
        }

        for (int i = st; i <= dr; ++ i )
            if (q[i].tip == 1)
                changed[q[i].who] = 0;
    }

    for (int i = 1; i <= Q; ++ i )
        if (q[i].tip == 2) cout << ans[i] << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void Return(int)':
bridges.cpp:65:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |     while (S.size() > sz) {
      |            ~~~~~~~~~^~~~
bridges.cpp: In function 'void Solve()':
bridges.cpp:130:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             while (ind < nemodif.size() && E[nemodif[ind]].weight >= q[itr].weight) {
      |                    ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27