Submission #246623

#	Time	Username	Problem	Language	Result	Execution time	Memory
246623		Kastanda	Bridges (APIO19_bridges)	C++11	100 / 100	2469 ms	8632 KiB

bridges

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 100005, SQ = 700;
int n, m, q, A[N], B[N], W[N], Rev[N];
int TP[N], V[N], Z[N], ME[N], Rs[N];
int P[N], P2[N], Fw[SQ + 5][SQ + 5];
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
int Find2(int v)
{
        return (P2[v] < 0 ? v : (P2[v] = Find2(P2[v])));
}
inline void Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v != u)
                P[v] += P[u], P[u] = v;
}
inline void Merge2(int v, int u)
{
        v = Find2(v);
        u = Find2(u);
        if (v != u)
                P2[v] += P2[u], P2[u] = v;
}
int main()
{
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i ++)
        {
                scanf("%d%d%d", &A[i], &B[i], &W[i]);
        }
        scanf("%d", &q);
        for (int i = 1; i <= q; i ++)
                scanf("%d%d%d", &TP[i], &V[i], &Z[i]);
        vector < int > E;
        for (int i = 1; i <= m; i ++)
                E.push_back(i);
        sort(E.begin(), E.end(), [&](int i, int j){return W[i] > W[j];});
        for (int l = 1; l <= q; l += SQ)
        {
                int r = min(l + SQ - 1, q);

                // Eliminating marked edges from E .. :
                for (int i = l; i <= r; i ++)
                        if (TP[i] == 1) ME[V[i]] = i;
                vector < int > tmpE, MarkE;
                for (int id : E)
                        if (!ME[id])
                                tmpE.push_back(id);
                        else
                                MarkE.push_back(id), Rev[id] = (int)MarkE.size() - 1;
                E.swap(tmpE);
                tmpE.clear();
                // Done with this thing

                vector < int > Q;
                for (int i = l; i <= r; i ++)
                        if (TP[i] == 2) Q.push_back(i);
                sort(Q.begin(), Q.end(), [&](int i, int j){return Z[i] > Z[j];});

                // Vertices of interset :
                vector < int > Voi;
                for (int i = l; i <= r; i ++)
                        if (TP[i] == 1)
                                Voi.push_back(A[V[i]]),
                                Voi.push_back(B[V[i]]);
                        else
                                Voi.push_back(V[i]);

                // Calculating last instance of each edge for each query ...
                vector < int > prev((int)MarkE.size());
                for (int i = 0; i < MarkE.size(); i ++)
                        prev[i] = W[MarkE[i]];
                for (int i = l; i <= r; i ++)
                {
                        if (TP[i] == 1)
                                prev[Rev[V[i]]] = Z[i];
                        else
                                for (int j = 0; j < (int)MarkE.size(); j ++)
                                        Fw[i - l][j] = prev[j];
                }
                // Phew, all done ...


                int ptre = 0;
                memset(P2, 0, sizeof(P2));
                memset(P, -1, sizeof(P));
                for (int i : Q)
                {
                        while (ptre < (int)E.size() && W[E[ptre]] >= Z[i])
                                Merge(A[E[ptre]], B[E[ptre]]), ptre ++;
                        for (int v : Voi)
                                Find(v), P2[v] = P[v], P2[Find(v)] = P[Find(v)];

                        for (int j = 0; j < (int)MarkE.size(); j ++)
                                if (Fw[i - l][j] >= Z[i])
                                        Merge2(A[MarkE[j]], B[MarkE[j]]);

                        Rs[i] = - P2[Find2(V[i])];
                }

                for (int i = l; i <= r; i ++)
                        if (TP[i] == 1)
                                ME[V[i]] = 0, W[V[i]] = Z[i];

                sort(MarkE.begin(), MarkE.end(), [&](int i, int j){return W[i] > W[j];});

                int ptme = 0;
                tmpE.clear();
                for (int e : E)
                {
                        while (ptme < (int)MarkE.size() && W[MarkE[ptme]] > W[e])
                                tmpE.push_back(MarkE[ptme]), ptme ++;
                        tmpE.push_back(e);
                }
                while (ptme < (int)MarkE.size())
                        tmpE.push_back(MarkE[ptme]), ptme ++;
                E.swap(tmpE);
                tmpE.clear();
                assert((int)E.size() == m);

        }

        for (int i = 1; i <= q; i ++)
                if (TP[i] == 2)
                        printf("%d\n", Rs[i]);
        return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:77:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < MarkE.size(); i ++)
                                 ~~^~~~~~~~~~~~~~
bridges.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &m);
         ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:35:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d%d", &A[i], &B[i], &W[i]);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &q);
         ~~~~~^~~~~~~~~~
bridges.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d%d", &TP[i], &V[i], &Z[i]);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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