Submission #124495

#	Time	Username	Problem	Language	Result	Execution time	Memory
124495		EntityIT	Bridges (APIO19_bridges)	C++14	100 / 100	2339 ms	15624 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

const int N = (int)5e4 + 5, M = (int)1e5 + 5, Q = M, NGU = 320;
int n, m, q, ans[Q], nE, nVec, contain[N], nContain, lst[M];
vector<int> gr[N];
bool vis[N];

struct Edge {
    int u, v, d;
    Edge (int _u = 0, int _v = 0, int _d = 0) : u(_u), v(_v), d(_d) {}
    bool operator< (const Edge &_) const { return d > _.d; }
} edge[M], edge_[M], e[M];
vector< pair<Edge, pair<int, int> > > vecEdge;

struct Query {
    int t, id, r;
    Query (int _t = 0, int _id = 0, int _r = 0) : t(_t), id(_id), r(_r) {}
    bool operator< (const Query &_) const { return r > _.r; }
} query[Q];
pair<Query, int> vec[NGU + 5];

struct Dsu {
    int pSet[N], szSet[N];
    void init () {
        for (int i = 1; i <= n; ++i) pSet[i] = i, szSet[i] = 1;
    }
    int findSet (int i) { return i == pSet[i] ? i : pSet[i] = findSet(pSet[i]); }
    void unionSet (int i, int j) {
        i = findSet(i); j = findSet(j);
        if (i == j) return ;
        if (szSet[i] > szSet[j]) swap(i, j);
        szSet[j] += szSet[i];
        pSet[i] = j;
    }
} dsu;

void dfs (int u) {
    if (vis[u]) return ;
    vis[u] = 1; contain[nContain++] = u;
    for (int v : gr[u]) dfs(v);
}

int main () {
//    freopen("test.INP", "r", stdin);
    scanf("%d %d", &n, &m);
    memset(lst, -1, sizeof lst);
    for (int i = 1; i <= m; ++i) {
        int u, v, d; scanf("%d %d %d", &u, &v, &d);
        edge_[i] = edge[i] = Edge(u, v, d);
        vecEdge.pb( { edge[i], { i, -1 } } );
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i) {
        int t, id, r; scanf("%d %d %d", &t, &id, &r);
        query[i] = Query(t, id, r);
        if (t == 1) {
            vecEdge.pb( { Edge(edge[id].u, edge[id].v, r), { id, i } } );
        }
    }
    sort(vecEdge.begin(), vecEdge.end() );

    for (int i = 1; i <= q; i += NGU) {
        dsu.init();
        nVec = 0;
        vector<bool> exist(M);
        for (int j = i; j <= min(q, i + NGU - 1); ++j) {
            if (query[j].t == 2) vec[nVec++] = { query[j], j };
            else exist[ query[j].id ] = 1;
        }
        sort(vec, vec + nVec);
        nE = 0;
        for (auto _ : vecEdge) if (!exist[_.se.fi] && lst[_.se.fi] == _.se.se) e[nE++] = _.fi;

        int iE = 0;
        for (int _j = 0; _j < nVec; ++_j) {
            auto _ = vec[_j];
            Query _query = _.fi;
            for (; iE < nE && e[iE].d >= _query.r; ++iE) dsu.unionSet(e[iE].u, e[iE].v);
            for (int j = i; j <= _.se; ++j) if (query[j].t == 1) edge_[ query[j].id ].d = query[j].r;
            for (int j = i; j <= min(q, i + NGU - 1); ++j) if (query[j].t == 1 && edge_[ query[j].id ].d >= _query.r) {
                gr[ dsu.findSet(edge[ query[j].id ].u) ].pb(dsu.findSet(edge[ query[j].id ].v) );
                gr[ dsu.findSet(edge[ query[j].id ].v) ].pb(dsu.findSet(edge[ query[j].id ].u) );
            }
            dfs(dsu.findSet(_query.id) );
            for (int _k = 0; _k < nContain; ++_k) {
                int __ = contain[_k];
                ans[_.se] += dsu.szSet[__];
                vis[__] = 0;
            }
            nContain = 0;
            for (int j = i; j <= min(q, i + NGU - 1); ++j) if (query[j].t == 1 && edge_[ query[j].id ].d >= _query.r) {
                gr[ dsu.findSet(edge[ query[j].id ].u) ].clear();
                gr[ dsu.findSet(edge[ query[j].id ].v) ].clear();
            }
            for (int j = i; j <= _.se; ++j) if (query[j].t == 1) edge_[ query[j].id ].d = edge[ query[j].id ].d;
        }


        for (int j = i; j <= min(q, i + NGU - 1); ++j) if (query[j].t == 1) edge_[ query[j].id ].d = edge[ query[j].id ].d = query[j].r, lst[ query[j].id ] = j;
    }

    for (int i = 1; i <= q; ++i) if (query[i].t == 2) printf("%d\n", ans[i]);

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:54:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, d; scanf("%d %d %d", &u, &v, &d);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
bridges.cpp:60:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t, id, r; scanf("%d %d %d", &t, &id, &r);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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