oj.uz

Submission #125243

# Submission time Handle Problem Language Result Execution time Memory
125243 2019-07-04T22:00:09 Z tri Bridges (APIO19_bridges) C++14
100 / 100
 2108 ms 17736 KB 
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef tuple<int, int, int, int, int> edge; // weight, startTime, endTime, endpts (x2)
typedef tuple<int, int, int> query; // weight, time, pt

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int BLKSZ = 400;
const int NUMBLKS = 100000 / BLKSZ + 5;

const int MAXN = 50100;

struct DSU {
    int anc[MAXN], sz[MAXN], rank[MAXN];

    void init() {
        for (int i = 0; i < MAXN; i++) {
            anc[i] = i;
            sz[i] = 1;
            rank[i] = 0;
        }
    }

    int fRt(int i) {
        return anc[i] == i ? i : anc[i] = fRt(anc[i]);
    }

    bool merge(int a, int b) { // TODO: implement rank
        a = fRt(a), b = fRt(b);
        if (a == b) {
            return false;
        }
        if (rank[a] < rank[b]) {
            anc[a] = b;
            sz[b] += sz[a];
        } else if (rank[a] > rank[b]) {
            anc[b] = a;
            sz[a] += sz[b];
        }
        else{
            anc[b] = a;
            sz[a] += sz[b];
            rank[a]++;
        }

        return true;
    }
} ds;

vector<vi> aList;
vector<bool> vis;
vector<int> undo;
int cnt = 0;

void dfs(int cV) {
    vis[cV] = true;
    cnt += ds.sz[cV];
    for (int aV : aList[cV]) {
        if (!vis[aV]) {
            dfs(aV);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("bridges.in", "r", stdin);

    int V, E, Q;
    cin >> V >> E;

    vector<edge> edges;
    vector<pi> endP(E);
    vi sT(E);
    vi lW(E);

    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        endP[i] = {u, v};
        sT[i] = -1;
        lW[i] = w;
    }

    cin >> Q;

    vector<vector<query>> qBlks(NUMBLKS);
    vector<vector<edge>> eBlks(NUMBLKS);

    for (int cT = 0; cT < Q; cT++) {
        int t, x, w;
        cin >> t >> x >> w;
        x--;
        if (t == 1) {
            edge cE = {lW[x], sT[x], cT - 1, endP[x].f, endP[x].s};

            edges.pb(cE);
            eBlks[sT[x] / BLKSZ].pb(cE);
            eBlks[(cT - 1) / BLKSZ].pb(cE);

            sT[x] = cT;
            lW[x] = w;
        } else {
            qBlks[cT / BLKSZ].pb({w, cT, x});
        }
    }

    for (int x = 0; x < E; x++) {
        edge cE = {lW[x], sT[x], 100005, endP[x].f, endP[x].s};
        edges.pb(cE);
        eBlks[sT[x] / BLKSZ].pb(cE);
        eBlks[100005 / BLKSZ].pb(cE);
    }

    edges.pb({-1, -1, -1, -1, -1}); // dummy edge with weight -1 to make sure all queries are processed

    sort(edges.begin(), edges.end());
    reverse(edges.begin(), edges.end());
    // decreasing weight

    aList.resize(V);
    vis.resize(V, false);

    vi qAns(Q, -1);

    for (int cBlk = 0; cBlk < NUMBLKS; cBlk++) {
        vector<query> &cQs = qBlks[cBlk];
        vector<edge> &cEs = eBlks[cBlk];

        sort(cQs.begin(), cQs.end());
        reverse(cQs.begin(), cQs.end());
        // decreasing weight

        int blkL = cBlk * BLKSZ;
        int blkR = (cBlk + 1) * BLKSZ - 1;

        ds.init();

        int nxtQ = 0;
        for (edge oE: edges) {
            int oW = get<0>(oE);
            int oST = get<1>(oE);
            int oET = get<2>(oE);
            int oU = get<3>(oE);
            int oV = get<4>(oE);

            while (nxtQ < cQs.size() && get<0>(cQs[nxtQ]) > oW) {
                int qW = get<0>(cQs[nxtQ]);
                int qT = get<1>(cQs[nxtQ]);
                int qPt = get<2>(cQs[nxtQ]);

                // we have components determined by ds and a set of extra edges

                for (edge iE : cEs) {
                    int iW = get<0>(iE);
                    int iST = get<1>(iE);
                    int iET = get<2>(iE);
                    int iU = ds.fRt(get<3>(iE));
                    int iV = ds.fRt(get<4>(iE));

                    if (iU == iV) { // useless
                        continue;
                    }

                    if (iST <= qT && qT <= iET && iW >= qW) { // usable iff within time zone and qW
                        aList[iU].pb(iV);
                        aList[iV].pb(iU);
                        undo.pb(iU);
                        undo.pb(iV);
                    }
                }

                dfs(ds.fRt(qPt));
                undo.pb(ds.fRt(qPt));

                qAns[qT] = cnt;


                for (int cV : undo) {
                    aList[cV].clear();
                    vis[cV] = false;
                }

                undo.clear();
                cnt = 0;

                nxtQ++;
            }

            // only consider edges that completely surround this block
            if (oST < blkL && blkR < oET) {
                // merge endpoints in disjoint set
                ds.merge(oU, oV);
            }
        }
    }

    for (int i = 0; i < Q; i++) {
        if (qAns[i] != -1) {
            cout << qAns[i] << '\n';
        }
    }
    cout << flush;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (nxtQ < cQs.size() && get<0>(cQs[nxtQ]) > oW) {
                    ~~~~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1016 KB Output is correct
2 Correct 29 ms 1016 KB Output is correct
3 Correct 59 ms 1656 KB Output is correct
4 Correct 33 ms 1272 KB Output is correct
5 Correct 99 ms 1640 KB Output is correct
6 Correct 59 ms 1528 KB Output is correct
7 Correct 64 ms 1588 KB Output is correct
8 Correct 60 ms 1656 KB Output is correct
9 Correct 70 ms 1528 KB Output is correct
10 Correct 60 ms 1528 KB Output is correct
11 Correct 62 ms 1528 KB Output is correct
12 Correct 68 ms 1532 KB Output is correct
13 Correct 68 ms 1644 KB Output is correct
14 Correct 64 ms 1528 KB Output is correct
15 Correct 66 ms 1604 KB Output is correct
16 Correct 62 ms 1548 KB Output is correct
17 Correct 61 ms 1528 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1508 ms 12196 KB Output is correct
2 Correct 1482 ms 12136 KB Output is correct
3 Correct 1487 ms 12184 KB Output is correct
4 Correct 1439 ms 12060 KB Output is correct
5 Correct 1456 ms 12184 KB Output is correct
6 Correct 1705 ms 12056 KB Output is correct
7 Correct 1612 ms 12008 KB Output is correct
8 Correct 1571 ms 12056 KB Output is correct
9 Correct 72 ms 3192 KB Output is correct
10 Correct 1377 ms 12204 KB Output is correct
11 Correct 1323 ms 12200 KB Output is correct
12 Correct 976 ms 9336 KB Output is correct
13 Correct 1324 ms 13912 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1178 ms 10100 KB Output is correct
2 Correct 739 ms 7144 KB Output is correct
3 Correct 1174 ms 10240 KB Output is correct
4 Correct 1121 ms 10136 KB Output is correct
5 Correct 72 ms 3196 KB Output is correct
6 Correct 1128 ms 10008 KB Output is correct
7 Correct 1049 ms 10012 KB Output is correct
8 Correct 996 ms 9880 KB Output is correct
9 Correct 706 ms 7712 KB Output is correct
10 Correct 686 ms 7600 KB Output is correct
11 Correct 954 ms 12244 KB Output is correct
12 Correct 929 ms 12376 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1502 ms 12220 KB Output is correct
2 Correct 74 ms 3448 KB Output is correct
3 Correct 618 ms 9040 KB Output is correct
4 Correct 629 ms 9192 KB Output is correct
5 Correct 1426 ms 12460 KB Output is correct
6 Correct 1505 ms 12276 KB Output is correct
7 Correct 1441 ms 12272 KB Output is correct
8 Correct 1035 ms 8276 KB Output is correct
9 Correct 1068 ms 8300 KB Output is correct
10 Correct 951 ms 8468 KB Output is correct
11 Correct 1543 ms 10424 KB Output is correct
12 Correct 1509 ms 10224 KB Output is correct
13 Correct 1348 ms 10476 KB Output is correct
14 Correct 1302 ms 12496 KB Output is correct
15 Correct 1394 ms 12528 KB Output is correct
16 Correct 1661 ms 12140 KB Output is correct
17 Correct 1685 ms 12272 KB Output is correct
18 Correct 1715 ms 12268 KB Output is correct
19 Correct 1721 ms 12180 KB Output is correct
20 Correct 1485 ms 11240 KB Output is correct
21 Correct 1450 ms 11244 KB Output is correct
22 Correct 1480 ms 12144 KB Output is correct
23 Correct 1243 ms 10784 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1508 ms 12196 KB Output is correct
2 Correct 1482 ms 12136 KB Output is correct
3 Correct 1487 ms 12184 KB Output is correct
4 Correct 1439 ms 12060 KB Output is correct
5 Correct 1456 ms 12184 KB Output is correct
6 Correct 1705 ms 12056 KB Output is correct
7 Correct 1612 ms 12008 KB Output is correct
8 Correct 1571 ms 12056 KB Output is correct
9 Correct 72 ms 3192 KB Output is correct
10 Correct 1377 ms 12204 KB Output is correct
11 Correct 1323 ms 12200 KB Output is correct
12 Correct 976 ms 9336 KB Output is correct
13 Correct 1324 ms 13912 KB Output is correct
14 Correct 1178 ms 10100 KB Output is correct
15 Correct 739 ms 7144 KB Output is correct
16 Correct 1174 ms 10240 KB Output is correct
17 Correct 1121 ms 10136 KB Output is correct
18 Correct 72 ms 3196 KB Output is correct
19 Correct 1128 ms 10008 KB Output is correct
20 Correct 1049 ms 10012 KB Output is correct
21 Correct 996 ms 9880 KB Output is correct
22 Correct 706 ms 7712 KB Output is correct
23 Correct 686 ms 7600 KB Output is correct
24 Correct 954 ms 12244 KB Output is correct
25 Correct 929 ms 12376 KB Output is correct
26 Correct 1526 ms 11968 KB Output is correct
27 Correct 1696 ms 12256 KB Output is correct
28 Correct 1667 ms 12184 KB Output is correct
29 Correct 1393 ms 11928 KB Output is correct
30 Correct 1818 ms 12200 KB Output is correct
31 Correct 1831 ms 12152 KB Output is correct
32 Correct 1816 ms 12188 KB Output is correct
33 Correct 1736 ms 12316 KB Output is correct
34 Correct 1770 ms 12312 KB Output is correct
35 Correct 1718 ms 11932 KB Output is correct
36 Correct 1460 ms 12104 KB Output is correct
37 Correct 1465 ms 12060 KB Output is correct
38 Correct 1448 ms 12032 KB Output is correct
39 Correct 1122 ms 9588 KB Output is correct
40 Correct 1145 ms 9612 KB Output is correct
41 Correct 1129 ms 9740 KB Output is correct
42 Correct 1445 ms 14540 KB Output is correct
43 Correct 1373 ms 14552 KB Output is correct
44 Correct 1415 ms 14440 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1016 KB Output is correct
2 Correct 29 ms 1016 KB Output is correct
3 Correct 59 ms 1656 KB Output is correct
4 Correct 33 ms 1272 KB Output is correct
5 Correct 99 ms 1640 KB Output is correct
6 Correct 59 ms 1528 KB Output is correct
7 Correct 64 ms 1588 KB Output is correct
8 Correct 60 ms 1656 KB Output is correct
9 Correct 70 ms 1528 KB Output is correct
10 Correct 60 ms 1528 KB Output is correct
11 Correct 62 ms 1528 KB Output is correct
12 Correct 68 ms 1532 KB Output is correct
13 Correct 68 ms 1644 KB Output is correct
14 Correct 64 ms 1528 KB Output is correct
15 Correct 66 ms 1604 KB Output is correct
16 Correct 62 ms 1548 KB Output is correct
17 Correct 61 ms 1528 KB Output is correct
18 Correct 1508 ms 12196 KB Output is correct
19 Correct 1482 ms 12136 KB Output is correct
20 Correct 1487 ms 12184 KB Output is correct
21 Correct 1439 ms 12060 KB Output is correct
22 Correct 1456 ms 12184 KB Output is correct
23 Correct 1705 ms 12056 KB Output is correct
24 Correct 1612 ms 12008 KB Output is correct
25 Correct 1571 ms 12056 KB Output is correct
26 Correct 72 ms 3192 KB Output is correct
27 Correct 1377 ms 12204 KB Output is correct
28 Correct 1323 ms 12200 KB Output is correct
29 Correct 976 ms 9336 KB Output is correct
30 Correct 1324 ms 13912 KB Output is correct
31 Correct 1178 ms 10100 KB Output is correct
32 Correct 739 ms 7144 KB Output is correct
33 Correct 1174 ms 10240 KB Output is correct
34 Correct 1121 ms 10136 KB Output is correct
35 Correct 72 ms 3196 KB Output is correct
36 Correct 1128 ms 10008 KB Output is correct
37 Correct 1049 ms 10012 KB Output is correct
38 Correct 996 ms 9880 KB Output is correct
39 Correct 706 ms 7712 KB Output is correct
40 Correct 686 ms 7600 KB Output is correct
41 Correct 954 ms 12244 KB Output is correct
42 Correct 929 ms 12376 KB Output is correct
43 Correct 1502 ms 12220 KB Output is correct
44 Correct 74 ms 3448 KB Output is correct
45 Correct 618 ms 9040 KB Output is correct
46 Correct 629 ms 9192 KB Output is correct
47 Correct 1426 ms 12460 KB Output is correct
48 Correct 1505 ms 12276 KB Output is correct
49 Correct 1441 ms 12272 KB Output is correct
50 Correct 1035 ms 8276 KB Output is correct
51 Correct 1068 ms 8300 KB Output is correct
52 Correct 951 ms 8468 KB Output is correct
53 Correct 1543 ms 10424 KB Output is correct
54 Correct 1509 ms 10224 KB Output is correct
55 Correct 1348 ms 10476 KB Output is correct
56 Correct 1302 ms 12496 KB Output is correct
57 Correct 1394 ms 12528 KB Output is correct
58 Correct 1661 ms 12140 KB Output is correct
59 Correct 1685 ms 12272 KB Output is correct
60 Correct 1715 ms 12268 KB Output is correct
61 Correct 1721 ms 12180 KB Output is correct
62 Correct 1485 ms 11240 KB Output is correct
63 Correct 1450 ms 11244 KB Output is correct
64 Correct 1480 ms 12144 KB Output is correct
65 Correct 1243 ms 10784 KB Output is correct
66 Correct 1526 ms 11968 KB Output is correct
67 Correct 1696 ms 12256 KB Output is correct
68 Correct 1667 ms 12184 KB Output is correct
69 Correct 1393 ms 11928 KB Output is correct
70 Correct 1818 ms 12200 KB Output is correct
71 Correct 1831 ms 12152 KB Output is correct
72 Correct 1816 ms 12188 KB Output is correct
73 Correct 1736 ms 12316 KB Output is correct
74 Correct 1770 ms 12312 KB Output is correct
75 Correct 1718 ms 11932 KB Output is correct
76 Correct 1460 ms 12104 KB Output is correct
77 Correct 1465 ms 12060 KB Output is correct
78 Correct 1448 ms 12032 KB Output is correct
79 Correct 1122 ms 9588 KB Output is correct
80 Correct 1145 ms 9612 KB Output is correct
81 Correct 1129 ms 9740 KB Output is correct
82 Correct 1445 ms 14540 KB Output is correct
83 Correct 1373 ms 14552 KB Output is correct
84 Correct 1415 ms 14440 KB Output is correct
85 Correct 1914 ms 16536 KB Output is correct
86 Correct 559 ms 9308 KB Output is correct
87 Correct 552 ms 9308 KB Output is correct
88 Correct 1513 ms 16512 KB Output is correct
89 Correct 1850 ms 16588 KB Output is correct
90 Correct 1519 ms 16536 KB Output is correct
91 Correct 1721 ms 12440 KB Output is correct
92 Correct 1692 ms 12312 KB Output is correct
93 Correct 1819 ms 12056 KB Output is correct
94 Correct 1961 ms 13956 KB Output is correct
95 Correct 2005 ms 14200 KB Output is correct
96 Correct 1655 ms 14008 KB Output is correct
97 Correct 1449 ms 13580 KB Output is correct
98 Correct 1346 ms 17736 KB Output is correct
99 Correct 2044 ms 16536 KB Output is correct
100 Correct 1999 ms 16404 KB Output is correct
101 Correct 2088 ms 16536 KB Output is correct
102 Correct 2108 ms 16384 KB Output is correct
103 Correct 1726 ms 16276 KB Output is correct
104 Correct 1743 ms 16408 KB Output is correct
105 Correct 1807 ms 16428 KB Output is correct
106 Correct 1679 ms 16208 KB Output is correct
107 Correct 1553 ms 11836 KB Output is correct
108 Correct 1772 ms 16420 KB Output is correct
109 Correct 1361 ms 14488 KB Output is correct