oj.uz

Submission #129782

# Submission time Handle Problem Language Result Execution time Memory
129782 2019-07-13T08:20:06 Z pr3pony Bridges (APIO19_bridges) C++14
44 / 100
 3000 ms 162196 KB 
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x)   (std::isinf(x))
#define IS_NAN(x)   (std::isnan(x))
#define fi   first
#define se   second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }

/* Author: Van Hanh Pham */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

class DisjointSet {
private:
    int n;
    int *lab;

public:
    DisjointSet(int n = 0) {
        this->n = n;
        lab = NULL;
        if (n > 0) lab = new int[n + 3];
        FOR(i, 1, n) lab[i] = -1;
    }

    int find(int x) {
        return lab[x] < 0 ? x : lab[x] = find(lab[x]);
    }

    bool join(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x == y) return false;
        if (lab[x] > lab[y]) swap(x, y);
        lab[x] += lab[y];
        lab[y] = x;
        return true;
    }

    int getSize(int x) {
        return -lab[find(x)];
    }

    void reset(void) {
        FOR(i, 1, n) lab[i] = -1;
    }

    void assign(int n) {
        this->n = n;
        reset();
    }
};

struct Edge {
    int u, v, cost;
    bool isStatic;

    Edge(int _u = 0, int _v = 0, int _cost = 0) {
        u = _u; v = _v; cost = _cost; isStatic = false;
    }
};

#define UPDATE   1
#define ASK   2
struct Query {
    int type, id, cost, answer;
    int *tmpCost;

    Query() {
        type = id = cost = answer = 0; tmpCost = NULL;
    }

    void input(void) {
        assert(scanf("%d%d%d", &type, &id, &cost) == 3);
    }

    bool goodEdge(int index) {
        return tmpCost[index] >= cost;
    }
};

class ReverseCompare {
public:
    bool operator () (const pair<int, int> &a, const pair<int, int> &b) const {
        return a.fi == b.fi ? a.se > b.se : a.fi > b.fi;
    }
};

#define MAX   100100
#define BLOCK    444

int numNode, numEdge, numQuery;
Edge edges[MAX];
Query queries[MAX];
vector<int> updates, asks, tmpEdges;
set<pair<int, int>, ReverseCompare> orderByCost;
DisjointSet dsu, tmpDSU;
int tmpNodeID[MAX], numTmpNode;

void loadTree(void) {
    int task; scanf("%d%d", &numNode, &numEdge);
    FOR(i, 1, numEdge) {
        int u, v, c; scanf("%d%d%d", &u, &v, &c);
        edges[i] = Edge(u, v, c);
    }

    scanf("%d", &numQuery);
    FOR(i, 1, numQuery) {
        queries[i].input();
        if (queries[i].type == UPDATE) updates.push_back(i);
    }
}

void prepare(void) {
    FOR(i, 1, numEdge) orderByCost.insert(make_pair(edges[i].cost, i));
    dsu = DisjointSet(numNode);
    tmpDSU = DisjointSet(numNode);
}

bool CompareAsk(const int &x, const int &y) {
    return queries[x].cost > queries[y].cost;
}

void processBlock(int l, int r) { // all queries from l to r - 1
    asks.clear(); tmpEdges.clear();
    FOR(i, 1, numEdge) edges[i].isStatic = true;

    FOR(i, l, r - 1) {
        if (queries[i].type == UPDATE) {
            int j = queries[i].id;
            if (edges[j].isStatic) {
                edges[j].isStatic = false;
                tmpEdges.push_back(j);
            }
        } else asks.push_back(i);
    }

    FOR(i, l, r - 1) {
        if (queries[i].type == UPDATE) {
            int j = queries[i].id;
            orderByCost.erase(make_pair(edges[j].cost, j));
            edges[j].cost = queries[i].cost;
            orderByCost.insert(make_pair(edges[j].cost, j));
        } else {
            queries[i].tmpCost = new int[tmpEdges.size()];
            REP(j, tmpEdges.size()) queries[i].tmpCost[j] = edges[tmpEdges[j]].cost;
        }
    }

    dsu.reset();
    __typeof(orderByCost.begin()) ut = orderByCost.begin();
    sort(ALL(asks), CompareAsk);

    FORE(it, asks) {
        while (ut != orderByCost.end() && ut->fi >= queries[*it].cost) {
            if (edges[ut->se].isStatic) dsu.join(edges[ut->se].u, edges[ut->se].v);
            ut++;
        }

        numTmpNode = 0;
        REP(j, tmpEdges.size()) if (queries[*it].goodEdge(j)) {
            int jd = tmpEdges[j];
            int x = dsu.find(edges[jd].u);
            if (tmpNodeID[x] == 0) tmpNodeID[x] = ++numTmpNode;
            x = dsu.find(edges[jd].v);
            if (tmpNodeID[x] == 0) tmpNodeID[x] = ++numTmpNode;
        }
        if (tmpNodeID[dsu.find(queries[*it].id)] == 0) {
            queries[*it].answer = dsu.getSize(queries[*it].id);
            REP(j, tmpEdges.size()) if (queries[*it].goodEdge(j)) {
                int jd = tmpEdges[j];
                int x = dsu.find(edges[jd].u);
                int y = dsu.find(edges[jd].v);
                tmpNodeID[x] = tmpNodeID[y] = 0;
            }
        } else {
            tmpDSU.assign(numTmpNode);
            REP(j, tmpEdges.size()) if (queries[*it].goodEdge(j)) {
                int jd = tmpEdges[j];
                int x = dsu.find(edges[jd].u);
                int y = dsu.find(edges[jd].v);
                tmpDSU.join(tmpNodeID[x], tmpNodeID[y]);
            }
            int tmp = tmpDSU.find(tmpNodeID[dsu.find(queries[*it].id)]);
            REP(j, tmpEdges.size()) if (queries[*it].goodEdge(j)) {
                int jd = tmpEdges[j];
                int x = dsu.find(edges[jd].u);
                int y = dsu.find(edges[jd].v);
                if (tmpNodeID[x] > 0) {
                    if (tmpDSU.find(tmpNodeID[x]) == tmp) queries[*it].answer += dsu.getSize(x);
                    tmpNodeID[x] = 0;
                }
                if (tmpNodeID[y] > 0) {
                    if (tmpDSU.find(tmpNodeID[y]) == tmp) queries[*it].answer += dsu.getSize(y);
                    tmpNodeID[y] = 0;
                }
            }
        }
    }
}

void process(void) {
    if (queries[1].type != UPDATE) processBlock(1, updates.empty() ? numQuery + 1 : updates[0]);

    int i = 0;
    while (i < updates.size()) {
        int j = i + BLOCK;
        processBlock(updates[i], j < updates.size() ? updates[j] : numQuery + 1);
        i = j;
    }
    FOR(i, 1, numQuery) if (queries[i].type == ASK) printf("%d\n", queries[i].answer);
}

int main(void) {
#ifdef SKY
    freopen("tmp.txt", "r", stdin);
#endif // SKY
    loadTree();
    prepare();
    process();
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/

Compilation message

bridges.cpp: In function 'void loadTree()':
bridges.cpp:133:9: warning: unused variable 'task' [-Wunused-variable]
     int task; scanf("%d%d", &numNode, &numEdge);
         ^~~~
bridges.cpp: In function 'void process()':
bridges.cpp:238:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < updates.size()) {
            ~~^~~~~~~~~~~~~~~~
bridges.cpp:240:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         processBlock(updates[i], j < updates.size() ? updates[j] : numQuery + 1);
                                  ~~^~~~~~~~~~~~~~~~
bridges.cpp: In function 'void loadTree()':
bridges.cpp:133:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int task; scanf("%d%d", &numNode, &numEdge);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:135:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, c; scanf("%d%d%d", &u, &v, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:139:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &numQuery);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 65 ms 11380 KB Output is correct
4 Correct 11 ms 4728 KB Output is correct
5 Correct 25 ms 6264 KB Output is correct
6 Correct 21 ms 6264 KB Output is correct
7 Correct 26 ms 6392 KB Output is correct
8 Correct 30 ms 6392 KB Output is correct
9 Correct 30 ms 6264 KB Output is correct
10 Correct 29 ms 6392 KB Output is correct
11 Correct 29 ms 6392 KB Output is correct
12 Correct 33 ms 6392 KB Output is correct
13 Correct 40 ms 7288 KB Output is correct
14 Correct 37 ms 7288 KB Output is correct
15 Correct 34 ms 6520 KB Output is correct
16 Correct 28 ms 6392 KB Output is correct
17 Correct 28 ms 6392 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1911 ms 95040 KB Output is correct
2 Correct 1842 ms 94900 KB Output is correct
3 Correct 1794 ms 95020 KB Output is correct
4 Correct 1762 ms 95084 KB Output is correct
5 Correct 1747 ms 94972 KB Output is correct
6 Execution timed out 3031 ms 88380 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1453 ms 94044 KB Output is correct
2 Correct 1406 ms 90732 KB Output is correct
3 Correct 2107 ms 94004 KB Output is correct
4 Correct 1500 ms 94068 KB Output is correct
5 Correct 69 ms 8304 KB Output is correct
6 Correct 1733 ms 94220 KB Output is correct
7 Correct 1322 ms 94068 KB Output is correct
8 Correct 1151 ms 94196 KB Output is correct
9 Correct 2218 ms 161996 KB Output is correct
10 Correct 1527 ms 162196 KB Output is correct
11 Correct 952 ms 23920 KB Output is correct
12 Correct 837 ms 24128 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 13300 KB Output is correct
2 Correct 72 ms 7976 KB Output is correct
3 Correct 112 ms 9256 KB Output is correct
4 Correct 67 ms 9336 KB Output is correct
5 Correct 133 ms 13300 KB Output is correct
6 Correct 188 ms 13388 KB Output is correct
7 Correct 126 ms 13288 KB Output is correct
8 Correct 127 ms 10756 KB Output is correct
9 Correct 124 ms 10740 KB Output is correct
10 Correct 129 ms 10856 KB Output is correct
11 Correct 156 ms 11988 KB Output is correct
12 Correct 160 ms 12044 KB Output is correct
13 Correct 153 ms 12112 KB Output is correct
14 Correct 120 ms 13400 KB Output is correct
15 Correct 127 ms 13304 KB Output is correct
16 Correct 190 ms 13340 KB Output is correct
17 Correct 187 ms 13260 KB Output is correct
18 Correct 191 ms 13280 KB Output is correct
19 Correct 191 ms 13288 KB Output is correct
20 Correct 168 ms 12704 KB Output is correct
21 Correct 173 ms 12656 KB Output is correct
22 Correct 184 ms 13176 KB Output is correct
23 Correct 128 ms 12500 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1911 ms 95040 KB Output is correct
2 Correct 1842 ms 94900 KB Output is correct
3 Correct 1794 ms 95020 KB Output is correct
4 Correct 1762 ms 95084 KB Output is correct
5 Correct 1747 ms 94972 KB Output is correct
6 Execution timed out 3031 ms 88380 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 65 ms 11380 KB Output is correct
4 Correct 11 ms 4728 KB Output is correct
5 Correct 25 ms 6264 KB Output is correct
6 Correct 21 ms 6264 KB Output is correct
7 Correct 26 ms 6392 KB Output is correct
8 Correct 30 ms 6392 KB Output is correct
9 Correct 30 ms 6264 KB Output is correct
10 Correct 29 ms 6392 KB Output is correct
11 Correct 29 ms 6392 KB Output is correct
12 Correct 33 ms 6392 KB Output is correct
13 Correct 40 ms 7288 KB Output is correct
14 Correct 37 ms 7288 KB Output is correct
15 Correct 34 ms 6520 KB Output is correct
16 Correct 28 ms 6392 KB Output is correct
17 Correct 28 ms 6392 KB Output is correct
18 Correct 1911 ms 95040 KB Output is correct
19 Correct 1842 ms 94900 KB Output is correct
20 Correct 1794 ms 95020 KB Output is correct
21 Correct 1762 ms 95084 KB Output is correct
22 Correct 1747 ms 94972 KB Output is correct
23 Execution timed out 3031 ms 88380 KB Time limit exceeded
24 Halted 0 ms 0 KB -