Submission #124495

# Submission time Handle Problem Language Result Execution time Memory
124495 2019-07-03T12:15:41 Z EntityIT Bridges (APIO19_bridges) C++14
100 / 100
2339 ms 15624 KB
#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

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);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 7 ms 6648 KB Output is correct
2 Correct 7 ms 6648 KB Output is correct
3 Correct 47 ms 7128 KB Output is correct
4 Correct 21 ms 6776 KB Output is correct
5 Correct 52 ms 7160 KB Output is correct
6 Correct 44 ms 7048 KB Output is correct
7 Correct 43 ms 7000 KB Output is correct
8 Correct 44 ms 7160 KB Output is correct
9 Correct 52 ms 7000 KB Output is correct
10 Correct 43 ms 7056 KB Output is correct
11 Correct 43 ms 7144 KB Output is correct
12 Correct 46 ms 7132 KB Output is correct
13 Correct 48 ms 7032 KB Output is correct
14 Correct 46 ms 7032 KB Output is correct
15 Correct 49 ms 7056 KB Output is correct
16 Correct 46 ms 7032 KB Output is correct
17 Correct 45 ms 7000 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1517 ms 13600 KB Output is correct
2 Correct 1471 ms 13564 KB Output is correct
3 Correct 1477 ms 13656 KB Output is correct
4 Correct 1457 ms 13704 KB Output is correct
5 Correct 1428 ms 13668 KB Output is correct
6 Correct 1827 ms 12840 KB Output is correct
7 Correct 1760 ms 12484 KB Output is correct
8 Correct 1738 ms 12564 KB Output is correct
9 Correct 143 ms 8568 KB Output is correct
10 Correct 1271 ms 12592 KB Output is correct
11 Correct 1225 ms 12508 KB Output is correct
12 Correct 986 ms 11936 KB Output is correct
13 Correct 1256 ms 14564 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1214 ms 12432 KB Output is correct
2 Correct 795 ms 10300 KB Output is correct
3 Correct 1299 ms 12248 KB Output is correct
4 Correct 1155 ms 12576 KB Output is correct
5 Correct 143 ms 8568 KB Output is correct
6 Correct 1202 ms 12284 KB Output is correct
7 Correct 1058 ms 12376 KB Output is correct
8 Correct 965 ms 12516 KB Output is correct
9 Correct 703 ms 11244 KB Output is correct
10 Correct 659 ms 11164 KB Output is correct
11 Correct 876 ms 13068 KB Output is correct
12 Correct 790 ms 13040 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1234 ms 13720 KB Output is correct
2 Correct 144 ms 8748 KB Output is correct
3 Correct 103 ms 10608 KB Output is correct
4 Correct 89 ms 10728 KB Output is correct
5 Correct 1102 ms 12324 KB Output is correct
6 Correct 1210 ms 13960 KB Output is correct
7 Correct 1127 ms 12380 KB Output is correct
8 Correct 893 ms 11452 KB Output is correct
9 Correct 908 ms 11628 KB Output is correct
10 Correct 896 ms 11484 KB Output is correct
11 Correct 1236 ms 12612 KB Output is correct
12 Correct 1216 ms 12600 KB Output is correct
13 Correct 1249 ms 12576 KB Output is correct
14 Correct 1102 ms 12288 KB Output is correct
15 Correct 1135 ms 12252 KB Output is correct
16 Correct 1442 ms 13764 KB Output is correct
17 Correct 1463 ms 13644 KB Output is correct
18 Correct 1438 ms 13760 KB Output is correct
19 Correct 1527 ms 13900 KB Output is correct
20 Correct 1367 ms 13100 KB Output is correct
21 Correct 1346 ms 12896 KB Output is correct
22 Correct 1420 ms 13680 KB Output is correct
23 Correct 1162 ms 11680 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1517 ms 13600 KB Output is correct
2 Correct 1471 ms 13564 KB Output is correct
3 Correct 1477 ms 13656 KB Output is correct
4 Correct 1457 ms 13704 KB Output is correct
5 Correct 1428 ms 13668 KB Output is correct
6 Correct 1827 ms 12840 KB Output is correct
7 Correct 1760 ms 12484 KB Output is correct
8 Correct 1738 ms 12564 KB Output is correct
9 Correct 143 ms 8568 KB Output is correct
10 Correct 1271 ms 12592 KB Output is correct
11 Correct 1225 ms 12508 KB Output is correct
12 Correct 986 ms 11936 KB Output is correct
13 Correct 1256 ms 14564 KB Output is correct
14 Correct 1214 ms 12432 KB Output is correct
15 Correct 795 ms 10300 KB Output is correct
16 Correct 1299 ms 12248 KB Output is correct
17 Correct 1155 ms 12576 KB Output is correct
18 Correct 143 ms 8568 KB Output is correct
19 Correct 1202 ms 12284 KB Output is correct
20 Correct 1058 ms 12376 KB Output is correct
21 Correct 965 ms 12516 KB Output is correct
22 Correct 703 ms 11244 KB Output is correct
23 Correct 659 ms 11164 KB Output is correct
24 Correct 876 ms 13068 KB Output is correct
25 Correct 790 ms 13040 KB Output is correct
26 Correct 1648 ms 13592 KB Output is correct
27 Correct 1854 ms 13540 KB Output is correct
28 Correct 1688 ms 13620 KB Output is correct
29 Correct 1375 ms 13596 KB Output is correct
30 Correct 1866 ms 13464 KB Output is correct
31 Correct 1991 ms 13564 KB Output is correct
32 Correct 1886 ms 13548 KB Output is correct
33 Correct 1707 ms 13836 KB Output is correct
34 Correct 1731 ms 13592 KB Output is correct
35 Correct 1741 ms 13668 KB Output is correct
36 Correct 1465 ms 13464 KB Output is correct
37 Correct 1438 ms 13488 KB Output is correct
38 Correct 1452 ms 13488 KB Output is correct
39 Correct 1054 ms 12304 KB Output is correct
40 Correct 1048 ms 12128 KB Output is correct
41 Correct 1091 ms 12268 KB Output is correct
42 Correct 1183 ms 14564 KB Output is correct
43 Correct 1182 ms 14564 KB Output is correct
44 Correct 1147 ms 14564 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 6648 KB Output is correct
2 Correct 7 ms 6648 KB Output is correct
3 Correct 47 ms 7128 KB Output is correct
4 Correct 21 ms 6776 KB Output is correct
5 Correct 52 ms 7160 KB Output is correct
6 Correct 44 ms 7048 KB Output is correct
7 Correct 43 ms 7000 KB Output is correct
8 Correct 44 ms 7160 KB Output is correct
9 Correct 52 ms 7000 KB Output is correct
10 Correct 43 ms 7056 KB Output is correct
11 Correct 43 ms 7144 KB Output is correct
12 Correct 46 ms 7132 KB Output is correct
13 Correct 48 ms 7032 KB Output is correct
14 Correct 46 ms 7032 KB Output is correct
15 Correct 49 ms 7056 KB Output is correct
16 Correct 46 ms 7032 KB Output is correct
17 Correct 45 ms 7000 KB Output is correct
18 Correct 1517 ms 13600 KB Output is correct
19 Correct 1471 ms 13564 KB Output is correct
20 Correct 1477 ms 13656 KB Output is correct
21 Correct 1457 ms 13704 KB Output is correct
22 Correct 1428 ms 13668 KB Output is correct
23 Correct 1827 ms 12840 KB Output is correct
24 Correct 1760 ms 12484 KB Output is correct
25 Correct 1738 ms 12564 KB Output is correct
26 Correct 143 ms 8568 KB Output is correct
27 Correct 1271 ms 12592 KB Output is correct
28 Correct 1225 ms 12508 KB Output is correct
29 Correct 986 ms 11936 KB Output is correct
30 Correct 1256 ms 14564 KB Output is correct
31 Correct 1214 ms 12432 KB Output is correct
32 Correct 795 ms 10300 KB Output is correct
33 Correct 1299 ms 12248 KB Output is correct
34 Correct 1155 ms 12576 KB Output is correct
35 Correct 143 ms 8568 KB Output is correct
36 Correct 1202 ms 12284 KB Output is correct
37 Correct 1058 ms 12376 KB Output is correct
38 Correct 965 ms 12516 KB Output is correct
39 Correct 703 ms 11244 KB Output is correct
40 Correct 659 ms 11164 KB Output is correct
41 Correct 876 ms 13068 KB Output is correct
42 Correct 790 ms 13040 KB Output is correct
43 Correct 1234 ms 13720 KB Output is correct
44 Correct 144 ms 8748 KB Output is correct
45 Correct 103 ms 10608 KB Output is correct
46 Correct 89 ms 10728 KB Output is correct
47 Correct 1102 ms 12324 KB Output is correct
48 Correct 1210 ms 13960 KB Output is correct
49 Correct 1127 ms 12380 KB Output is correct
50 Correct 893 ms 11452 KB Output is correct
51 Correct 908 ms 11628 KB Output is correct
52 Correct 896 ms 11484 KB Output is correct
53 Correct 1236 ms 12612 KB Output is correct
54 Correct 1216 ms 12600 KB Output is correct
55 Correct 1249 ms 12576 KB Output is correct
56 Correct 1102 ms 12288 KB Output is correct
57 Correct 1135 ms 12252 KB Output is correct
58 Correct 1442 ms 13764 KB Output is correct
59 Correct 1463 ms 13644 KB Output is correct
60 Correct 1438 ms 13760 KB Output is correct
61 Correct 1527 ms 13900 KB Output is correct
62 Correct 1367 ms 13100 KB Output is correct
63 Correct 1346 ms 12896 KB Output is correct
64 Correct 1420 ms 13680 KB Output is correct
65 Correct 1162 ms 11680 KB Output is correct
66 Correct 1648 ms 13592 KB Output is correct
67 Correct 1854 ms 13540 KB Output is correct
68 Correct 1688 ms 13620 KB Output is correct
69 Correct 1375 ms 13596 KB Output is correct
70 Correct 1866 ms 13464 KB Output is correct
71 Correct 1991 ms 13564 KB Output is correct
72 Correct 1886 ms 13548 KB Output is correct
73 Correct 1707 ms 13836 KB Output is correct
74 Correct 1731 ms 13592 KB Output is correct
75 Correct 1741 ms 13668 KB Output is correct
76 Correct 1465 ms 13464 KB Output is correct
77 Correct 1438 ms 13488 KB Output is correct
78 Correct 1452 ms 13488 KB Output is correct
79 Correct 1054 ms 12304 KB Output is correct
80 Correct 1048 ms 12128 KB Output is correct
81 Correct 1091 ms 12268 KB Output is correct
82 Correct 1183 ms 14564 KB Output is correct
83 Correct 1182 ms 14564 KB Output is correct
84 Correct 1147 ms 14564 KB Output is correct
85 Correct 2025 ms 15556 KB Output is correct
86 Correct 136 ms 10744 KB Output is correct
87 Correct 138 ms 10872 KB Output is correct
88 Correct 1785 ms 14180 KB Output is correct
89 Correct 2041 ms 15624 KB Output is correct
90 Correct 1818 ms 14052 KB Output is correct
91 Correct 1737 ms 13444 KB Output is correct
92 Correct 1701 ms 13716 KB Output is correct
93 Correct 1982 ms 12820 KB Output is correct
94 Correct 2107 ms 14472 KB Output is correct
95 Correct 2094 ms 14716 KB Output is correct
96 Correct 2173 ms 13668 KB Output is correct
97 Correct 1282 ms 12556 KB Output is correct
98 Correct 1562 ms 14536 KB Output is correct
99 Correct 2175 ms 15320 KB Output is correct
100 Correct 2271 ms 15348 KB Output is correct
101 Correct 2305 ms 15480 KB Output is correct
102 Correct 2339 ms 15596 KB Output is correct
103 Correct 2292 ms 15204 KB Output is correct
104 Correct 2289 ms 15100 KB Output is correct
105 Correct 2025 ms 14684 KB Output is correct
106 Correct 1786 ms 14568 KB Output is correct
107 Correct 1622 ms 13148 KB Output is correct
108 Correct 2299 ms 15176 KB Output is correct
109 Correct 1960 ms 12676 KB Output is correct