Submission #124432

#	Time	Username	Problem	Language	Result	Execution time	Memory
124432		EntityIT	Bridges (APIO19_bridges)	C++14	14 / 100	3021 ms	524292 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 = 300;
int n, m, q, ans[Q];
vector<int> gr[N], contain;
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];
vector< pair<Edge, 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];

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.pb(u);
    for (int v : gr[u]) dfs(v);
}

int main () {
//    freopen("test.INP", "r", stdin);
    scanf("%d %d", &n, &m);
    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 } );
    }
    sort(vecEdge.begin(), vecEdge.end() );
    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);
    }

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

        int iE = 0;
        for (auto _ : vec) {
            Query _query = _.fi;
//            cout << _.se << "*********\n";
            for (; iE < (int)e.size() && 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 __ : contain) {
                ans[_.se] += dsu.szSet[__];
                vis[__] = 0;
            }
            contain.clear();
            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;
        }

        while (1) {
            bool ok = 0;
            for (int j = 0; j < (int)vecEdge.size(); ++j) if (exist[ vecEdge[j].se ]) {
                vecEdge.erase(vecEdge.begin() + j); ok = 1;
                break ;
            }
            if (!ok) break ;
        }

        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;

        for (int j = 1; j <= m; ++j) if (exist[j]) {
            for (int k = 0; k <= (int)vecEdge.size(); ++k) {
                if (k == (int)vecEdge.size() ) vecEdge.insert(vecEdge.begin() + k, { edge[j], j } );
                else if (vecEdge[k].fi < edge[j]) {
                    vecEdge.insert(vecEdge.begin() + k, { edge[j], j } );
                    break ;
                }
            }
        }
    }

    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:50: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:52: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:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
bridges.cpp:59: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: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27