oj.uz

Submission #196964

# Submission time Handle Problem Language Result Execution time Memory
196964 2020-01-17T21:37:16 Z Akashi Bridges (APIO19_bridges) C++14
100 / 100
 2857 ms 12476 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int bucket_size = 700;

struct edges{
    int x, y, w, p, p2;
    bool operator < (const edges &aux)const{
        if(w != aux.w) return w > aux.w;
        return p < aux.p;
    }
};

inline bool cmp(edges a, edges b){
    return a.p < b.p;
}

struct query{
    int x, w, p;
    bool operator < (const query &aux)const{
        if(w != aux.w) return w > aux.w;
        return p < aux.p;
    }
};

edges a[M], e[M], b[2 * bucket_size + 5];
query Q[M];
int n, m, q;
bool uz[M], f[M];
int SZ[N], TT[N];
int tip[M], ans[M], Last[M];
vector <int> v[N];

inline int find(int x){
    int R = x;
    while(R != TT[R]) R = TT[R];
    while(x != R){
        int aux = TT[x];
        TT[x] = R;
        x = aux;
    }
    return R;
}

inline void unite(int x, int y){
    if(x == y) return ;
    if(SZ[x] > SZ[y]) SZ[x] += SZ[y], TT[y] = x;
    else SZ[y] += SZ[x], TT[x] = y;
}

bool viz[N];
int dfs(int nod){
    int ans = SZ[nod];
    viz[nod] = 1;
    for(auto it : v[nod]){
        if(viz[it]) continue ;
        ans += dfs(it);
    }
    return ans;
}
void bdfs(int nod){
    viz[nod] = 0;
    for(auto it : v[nod])
        if(viz[it]) bdfs(it);
}

int main()
{
//    freopen("1.in", "r", stdin);
//    freopen("1.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].w);
        a[i].p = i;
        e[i] = a[i];
    }

    scanf("%d", &q);
    int x, y, w;
    int i = 1;
    while(i <= q){
        memset(uz, 0, sizeof(uz));
        memset(Last, 0, sizeof(Last));
        sort(a + 1, a + m + 1);
        for(int i = 1; i <= n ; ++i) TT[i] = i, SZ[i] = 1;

        int k = 0, nr = 0;
        while(k <= bucket_size && i <= q){
            scanf("%d%d%d", &tip[i], &x, &w);
            if(tip[i] == 1){
                if(!uz[x]) b[++k] = {e[x].x, e[x].y, e[x].w, 0, i - 1};
                b[++k] = {e[x].x, e[x].y, w, i, q};

                if(Last[x]) b[Last[x]].p2 = i - 1;

                uz[x] = 1; Last[x] = k;
                e[x].w = w;
            }
            else Q[++nr] = {x, w, i};
            ++i;
        }

        sort(Q + 1, Q + nr + 1);
        sort(b + 1, b + k + 1, cmp);

        int j = 1;
        for(int i = 1; i <= nr ; ++i){
            while(j <= m && Q[i].w <= a[j].w){
                if(!uz[a[j].p]) unite(find(a[j].x), find(a[j].y));
                ++j;
            }

            for(int t = 1; t <= k ; ++t){
                if(b[t].p > Q[i].p) break ;
                if(b[t].w >= Q[i].w && (b[t].p <= Q[i].p && Q[i].p <= b[t].p2)){
                    x = find(b[t].x); y = find(b[t].y);
                    if(x != y){
                        v[x].push_back(y);
                        v[y].push_back(x);
                    }
                }
            }

            ans[Q[i].p] = dfs(find(Q[i].x));
            bdfs(find(Q[i].x));

            for(int t = 1; t <= k ; ++t){
                if(b[t].p > Q[i].p) break ;
                if(b[t].w >= Q[i].w && (b[t].p <= Q[i].p && Q[i].p <= b[t].p2)){
                    x = find(b[t].x); y = find(b[t].y);
                    if(x != y){
                        v[x].clear();
                        v[y].clear();
                    }
                }
            }
        }

        for(int i = 1; i <= m ; ++i) a[i].w = e[a[i].p].w;
    }

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

    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:75: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:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
bridges.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d", &tip[i], &x, &w);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 4 ms 2040 KB Output is correct
3 Correct 38 ms 2296 KB Output is correct
4 Correct 8 ms 2296 KB Output is correct
5 Correct 31 ms 2296 KB Output is correct
6 Correct 31 ms 2296 KB Output is correct
7 Correct 31 ms 2168 KB Output is correct
8 Correct 32 ms 2296 KB Output is correct
9 Correct 36 ms 2356 KB Output is correct
10 Correct 31 ms 2300 KB Output is correct
11 Correct 31 ms 2296 KB Output is correct
12 Correct 36 ms 2300 KB Output is correct
13 Correct 41 ms 2296 KB Output is correct
14 Correct 38 ms 2424 KB Output is correct
15 Correct 40 ms 2296 KB Output is correct
16 Correct 32 ms 2296 KB Output is correct
17 Correct 32 ms 2168 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 7704 KB Output is correct
2 Correct 1337 ms 7644 KB Output is correct
3 Correct 1330 ms 7844 KB Output is correct
4 Correct 1373 ms 7772 KB Output is correct
5 Correct 1332 ms 7608 KB Output is correct
6 Correct 2284 ms 7208 KB Output is correct
7 Correct 2025 ms 6836 KB Output is correct
8 Correct 1882 ms 7000 KB Output is correct
9 Correct 55 ms 4984 KB Output is correct
10 Correct 1875 ms 7608 KB Output is correct
11 Correct 1626 ms 7640 KB Output is correct
12 Correct 2299 ms 6812 KB Output is correct
13 Correct 1391 ms 6780 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 6352 KB Output is correct
2 Correct 938 ms 4640 KB Output is correct
3 Correct 1345 ms 6564 KB Output is correct
4 Correct 1098 ms 6388 KB Output is correct
5 Correct 56 ms 4984 KB Output is correct
6 Correct 1220 ms 6348 KB Output is correct
7 Correct 1000 ms 6392 KB Output is correct
8 Correct 868 ms 6264 KB Output is correct
9 Correct 1364 ms 6284 KB Output is correct
10 Correct 974 ms 5948 KB Output is correct
11 Correct 915 ms 6128 KB Output is correct
12 Correct 855 ms 6452 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 10424 KB Output is correct
2 Correct 56 ms 4960 KB Output is correct
3 Correct 62 ms 7520 KB Output is correct
4 Correct 55 ms 7544 KB Output is correct
5 Correct 102 ms 10256 KB Output is correct
6 Correct 122 ms 10360 KB Output is correct
7 Correct 103 ms 10328 KB Output is correct
8 Correct 92 ms 7928 KB Output is correct
9 Correct 92 ms 7996 KB Output is correct
10 Correct 91 ms 8056 KB Output is correct
11 Correct 108 ms 9032 KB Output is correct
12 Correct 109 ms 8952 KB Output is correct
13 Correct 105 ms 9164 KB Output is correct
14 Correct 99 ms 10264 KB Output is correct
15 Correct 102 ms 10360 KB Output is correct
16 Correct 122 ms 10044 KB Output is correct
17 Correct 124 ms 10108 KB Output is correct
18 Correct 117 ms 10104 KB Output is correct
19 Correct 124 ms 10192 KB Output is correct
20 Correct 111 ms 9592 KB Output is correct
21 Correct 109 ms 9852 KB Output is correct
22 Correct 117 ms 10232 KB Output is correct
23 Correct 95 ms 9780 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 7704 KB Output is correct
2 Correct 1337 ms 7644 KB Output is correct
3 Correct 1330 ms 7844 KB Output is correct
4 Correct 1373 ms 7772 KB Output is correct
5 Correct 1332 ms 7608 KB Output is correct
6 Correct 2284 ms 7208 KB Output is correct
7 Correct 2025 ms 6836 KB Output is correct
8 Correct 1882 ms 7000 KB Output is correct
9 Correct 55 ms 4984 KB Output is correct
10 Correct 1875 ms 7608 KB Output is correct
11 Correct 1626 ms 7640 KB Output is correct
12 Correct 2299 ms 6812 KB Output is correct
13 Correct 1391 ms 6780 KB Output is correct
14 Correct 1097 ms 6352 KB Output is correct
15 Correct 938 ms 4640 KB Output is correct
16 Correct 1345 ms 6564 KB Output is correct
17 Correct 1098 ms 6388 KB Output is correct
18 Correct 56 ms 4984 KB Output is correct
19 Correct 1220 ms 6348 KB Output is correct
20 Correct 1000 ms 6392 KB Output is correct
21 Correct 868 ms 6264 KB Output is correct
22 Correct 1364 ms 6284 KB Output is correct
23 Correct 974 ms 5948 KB Output is correct
24 Correct 915 ms 6128 KB Output is correct
25 Correct 855 ms 6452 KB Output is correct
26 Correct 1465 ms 8132 KB Output is correct
27 Correct 1680 ms 8456 KB Output is correct
28 Correct 1436 ms 8404 KB Output is correct
29 Correct 1044 ms 8616 KB Output is correct
30 Correct 1863 ms 8528 KB Output is correct
31 Correct 1907 ms 8516 KB Output is correct
32 Correct 1893 ms 8644 KB Output is correct
33 Correct 1545 ms 8544 KB Output is correct
34 Correct 1534 ms 8536 KB Output is correct
35 Correct 1618 ms 8528 KB Output is correct
36 Correct 1154 ms 8596 KB Output is correct
37 Correct 1123 ms 8388 KB Output is correct
38 Correct 1140 ms 8520 KB Output is correct
39 Correct 748 ms 7928 KB Output is correct
40 Correct 722 ms 7876 KB Output is correct
41 Correct 706 ms 8036 KB Output is correct
42 Correct 1289 ms 8548 KB Output is correct
43 Correct 1291 ms 8552 KB Output is correct
44 Correct 1264 ms 8628 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 4 ms 2040 KB Output is correct
3 Correct 38 ms 2296 KB Output is correct
4 Correct 8 ms 2296 KB Output is correct
5 Correct 31 ms 2296 KB Output is correct
6 Correct 31 ms 2296 KB Output is correct
7 Correct 31 ms 2168 KB Output is correct
8 Correct 32 ms 2296 KB Output is correct
9 Correct 36 ms 2356 KB Output is correct
10 Correct 31 ms 2300 KB Output is correct
11 Correct 31 ms 2296 KB Output is correct
12 Correct 36 ms 2300 KB Output is correct
13 Correct 41 ms 2296 KB Output is correct
14 Correct 38 ms 2424 KB Output is correct
15 Correct 40 ms 2296 KB Output is correct
16 Correct 32 ms 2296 KB Output is correct
17 Correct 32 ms 2168 KB Output is correct
18 Correct 1356 ms 7704 KB Output is correct
19 Correct 1337 ms 7644 KB Output is correct
20 Correct 1330 ms 7844 KB Output is correct
21 Correct 1373 ms 7772 KB Output is correct
22 Correct 1332 ms 7608 KB Output is correct
23 Correct 2284 ms 7208 KB Output is correct
24 Correct 2025 ms 6836 KB Output is correct
25 Correct 1882 ms 7000 KB Output is correct
26 Correct 55 ms 4984 KB Output is correct
27 Correct 1875 ms 7608 KB Output is correct
28 Correct 1626 ms 7640 KB Output is correct
29 Correct 2299 ms 6812 KB Output is correct
30 Correct 1391 ms 6780 KB Output is correct
31 Correct 1097 ms 6352 KB Output is correct
32 Correct 938 ms 4640 KB Output is correct
33 Correct 1345 ms 6564 KB Output is correct
34 Correct 1098 ms 6388 KB Output is correct
35 Correct 56 ms 4984 KB Output is correct
36 Correct 1220 ms 6348 KB Output is correct
37 Correct 1000 ms 6392 KB Output is correct
38 Correct 868 ms 6264 KB Output is correct
39 Correct 1364 ms 6284 KB Output is correct
40 Correct 974 ms 5948 KB Output is correct
41 Correct 915 ms 6128 KB Output is correct
42 Correct 855 ms 6452 KB Output is correct
43 Correct 122 ms 10424 KB Output is correct
44 Correct 56 ms 4960 KB Output is correct
45 Correct 62 ms 7520 KB Output is correct
46 Correct 55 ms 7544 KB Output is correct
47 Correct 102 ms 10256 KB Output is correct
48 Correct 122 ms 10360 KB Output is correct
49 Correct 103 ms 10328 KB Output is correct
50 Correct 92 ms 7928 KB Output is correct
51 Correct 92 ms 7996 KB Output is correct
52 Correct 91 ms 8056 KB Output is correct
53 Correct 108 ms 9032 KB Output is correct
54 Correct 109 ms 8952 KB Output is correct
55 Correct 105 ms 9164 KB Output is correct
56 Correct 99 ms 10264 KB Output is correct
57 Correct 102 ms 10360 KB Output is correct
58 Correct 122 ms 10044 KB Output is correct
59 Correct 124 ms 10108 KB Output is correct
60 Correct 117 ms 10104 KB Output is correct
61 Correct 124 ms 10192 KB Output is correct
62 Correct 111 ms 9592 KB Output is correct
63 Correct 109 ms 9852 KB Output is correct
64 Correct 117 ms 10232 KB Output is correct
65 Correct 95 ms 9780 KB Output is correct
66 Correct 1465 ms 8132 KB Output is correct
67 Correct 1680 ms 8456 KB Output is correct
68 Correct 1436 ms 8404 KB Output is correct
69 Correct 1044 ms 8616 KB Output is correct
70 Correct 1863 ms 8528 KB Output is correct
71 Correct 1907 ms 8516 KB Output is correct
72 Correct 1893 ms 8644 KB Output is correct
73 Correct 1545 ms 8544 KB Output is correct
74 Correct 1534 ms 8536 KB Output is correct
75 Correct 1618 ms 8528 KB Output is correct
76 Correct 1154 ms 8596 KB Output is correct
77 Correct 1123 ms 8388 KB Output is correct
78 Correct 1140 ms 8520 KB Output is correct
79 Correct 748 ms 7928 KB Output is correct
80 Correct 722 ms 7876 KB Output is correct
81 Correct 706 ms 8036 KB Output is correct
82 Correct 1289 ms 8548 KB Output is correct
83 Correct 1291 ms 8552 KB Output is correct
84 Correct 1264 ms 8628 KB Output is correct
85 Correct 1991 ms 10184 KB Output is correct
86 Correct 188 ms 6960 KB Output is correct
87 Correct 144 ms 6904 KB Output is correct
88 Correct 2021 ms 9216 KB Output is correct
89 Correct 1995 ms 9280 KB Output is correct
90 Correct 2001 ms 8820 KB Output is correct
91 Correct 1527 ms 7596 KB Output is correct
92 Correct 1474 ms 7628 KB Output is correct
93 Correct 1828 ms 7040 KB Output is correct
94 Correct 1702 ms 8512 KB Output is correct
95 Correct 1771 ms 8536 KB Output is correct
96 Correct 1630 ms 7588 KB Output is correct
97 Correct 1006 ms 8796 KB Output is correct
98 Correct 2857 ms 9060 KB Output is correct
99 Correct 2111 ms 12292 KB Output is correct
100 Correct 2009 ms 12080 KB Output is correct
101 Correct 2113 ms 12476 KB Output is correct
102 Correct 2161 ms 12464 KB Output is correct
103 Correct 1754 ms 10308 KB Output is correct
104 Correct 1752 ms 10276 KB Output is correct
105 Correct 2524 ms 9936 KB Output is correct
106 Correct 2232 ms 9624 KB Output is correct
107 Correct 958 ms 10300 KB Output is correct
108 Correct 1970 ms 11140 KB Output is correct
109 Correct 1755 ms 8972 KB Output is correct