oj.uz

Submission #555919

# Submission time Handle Problem Language Result Execution time Memory
555919 2022-05-01T19:25:13 Z status_coding Bridges (APIO19_bridges) C++14
100 / 100
 1784 ms 15092 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx2")

using namespace std;

struct edge
{
    int x, y, w;

    edge(int x, int y, int w)
    {
        this->x = x;
        this->y = y;
        this->w = w;
    }

    bool operator< (edge b) const
    {
        return w > b.w;
    }
};

struct askS
{
    int p, w, id;

    askS(int p, int w, int id)
    {
        this->p = p;
        this->w = w;
        this->id = id;
    }

    bool operator<(askS b) const
    {
        return w > b.w;
    }
};

int n,m,q,rad;

vector<edge> e;
bool isChanged[100005];

vector<pair<int, int>> dsuS;
int dsu[100005];
int sz[100005];

vector<askS> ask;
vector<edge> unchanged;
vector<int> changed;
vector<pair<int, int>> toMerge[1005];

int tip[100005], w[100005], id[100005], poz[100005];
int ans[100005];

int dsu_par(int x)
{
    while(dsu[x] != x)
        x = dsu[x];
    return x;
}

inline void dsu_merge(int x, int y)
{
    x = dsu_par(x);
    y = dsu_par(y);

    if(x == y)
        return;

    if(sz[y] > sz[x])
        swap(x, y);

    dsuS.push_back({x, y});

    dsu[y] = x;
    sz[x] += sz[y];
}

inline void dsu_rollback(int last)
{
    while((int)dsuS.size() > last)
    {
        int x = dsuS.back().first;
        int y = dsuS.back().second;
        dsuS.pop_back();

        sz[x] -= sz[y];
        dsu[y] = y;
    }
}

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

    cin>>n>>m;
    rad = 1000;

    e.push_back(edge(0, 0, 0));
    for(int i=1; i<=m; i++)
    {
        long long x, y, w;
        cin>>x>>y>>w;

        e.push_back(edge(x, y, w));
    }

    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>tip[i];

        if(tip[i] == 1)
            cin>>id[i]>>w[i];
        else
            cin>>poz[i]>>w[i];
    }

    for(int l=1; l<=q; l+=rad)
    {
        int r = min(l+rad-1, q);

        //cout<<"bucket: "<<l<<' '<<r<<'\n';

        changed.clear();
        unchanged.clear();
        ask.clear();

        dsuS.clear();
        for(int i=1;i<=n;i++)
        {
            dsu[i] = i;
            sz[i] = 1;
        }

        for(int i=0;i<=rad;i++)
            toMerge[i].clear();

        for(int i=1; i<=m; i++)
            isChanged[i] = false;


        for(int i=l; i<=r; i++)
        {
            if(tip[i] == 1)
            {
                if(!isChanged[ id[i] ])
                    changed.push_back(id[i]);

                isChanged[ id[i] ] = true;
            }
        }

        for(int i=l; i<=r; i++)
        {
            if(tip[i] == 1)
                e[ id[i] ].w = w[i];
            else
            {
                ask.push_back(askS( poz[i], w[i], i ));

                for(int id : changed)
                    if(e[id].w >= w[i])
                        toMerge[ i-l ].push_back({e[id].x, e[id].y});
            }
        }

        for(int i=1; i<=m; i++)
            if(!isChanged[i])
                unchanged.push_back(e[i]);

        sort(ask.begin(), ask.end());
        sort(unchanged.begin(), unchanged.end());

        int j=0;
        for(int i=0; i<(int)ask.size(); i++)
        {
            while(j < (int)unchanged.size() && unchanged[j].w >= ask[i].w)
            {
                dsu_merge(unchanged[j].x, unchanged[j].y);
                j++;
            }

            int last = dsuS.size();
            for(auto it : toMerge[ ask[i].id - l ])
                dsu_merge(it.first, it.second);

            ans[ ask[i].id ] = sz[ dsu_par(ask[i].p) ];

            dsu_rollback(last);
        }
    }

    //cout<<"\n\n";
    for(int i=1; i<=q; i++)
        if(tip[i] == 2)
            cout<<ans[i]<<'\n';

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 26 ms 4692 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 10 ms 1748 KB Output is correct
6 Correct 9 ms 1624 KB Output is correct
7 Correct 10 ms 1688 KB Output is correct
8 Correct 10 ms 1740 KB Output is correct
9 Correct 13 ms 1652 KB Output is correct
10 Correct 12 ms 1748 KB Output is correct
11 Correct 11 ms 1748 KB Output is correct
12 Correct 13 ms 1672 KB Output is correct
13 Correct 16 ms 2412 KB Output is correct
14 Correct 14 ms 2260 KB Output is correct
15 Correct 13 ms 1748 KB Output is correct
16 Correct 11 ms 1620 KB Output is correct
17 Correct 11 ms 1668 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 9496 KB Output is correct
2 Correct 1091 ms 10072 KB Output is correct
3 Correct 1053 ms 10096 KB Output is correct
4 Correct 1087 ms 10048 KB Output is correct
5 Correct 1067 ms 10484 KB Output is correct
6 Correct 1550 ms 13300 KB Output is correct
7 Correct 1519 ms 13292 KB Output is correct
8 Correct 1545 ms 13288 KB Output is correct
9 Correct 36 ms 2436 KB Output is correct
10 Correct 856 ms 13576 KB Output is correct
11 Correct 794 ms 13300 KB Output is correct
12 Correct 965 ms 6612 KB Output is correct
13 Correct 967 ms 12772 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 8828 KB Output is correct
2 Correct 550 ms 10688 KB Output is correct
3 Correct 925 ms 12844 KB Output is correct
4 Correct 777 ms 9380 KB Output is correct
5 Correct 38 ms 2452 KB Output is correct
6 Correct 871 ms 9412 KB Output is correct
7 Correct 713 ms 8836 KB Output is correct
8 Correct 648 ms 8760 KB Output is correct
9 Correct 535 ms 5436 KB Output is correct
10 Correct 503 ms 5324 KB Output is correct
11 Correct 567 ms 12476 KB Output is correct
12 Correct 509 ms 12480 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1298 ms 6064 KB Output is correct
2 Correct 38 ms 2840 KB Output is correct
3 Correct 147 ms 4668 KB Output is correct
4 Correct 87 ms 4752 KB Output is correct
5 Correct 769 ms 6872 KB Output is correct
6 Correct 1306 ms 6856 KB Output is correct
7 Correct 771 ms 6776 KB Output is correct
8 Correct 643 ms 5308 KB Output is correct
9 Correct 620 ms 5468 KB Output is correct
10 Correct 634 ms 5412 KB Output is correct
11 Correct 985 ms 6116 KB Output is correct
12 Correct 971 ms 6044 KB Output is correct
13 Correct 983 ms 6288 KB Output is correct
14 Correct 741 ms 6928 KB Output is correct
15 Correct 756 ms 6956 KB Output is correct
16 Correct 1311 ms 6856 KB Output is correct
17 Correct 1330 ms 6940 KB Output is correct
18 Correct 1314 ms 6892 KB Output is correct
19 Correct 1312 ms 6792 KB Output is correct
20 Correct 1093 ms 6576 KB Output is correct
21 Correct 1092 ms 6612 KB Output is correct
22 Correct 1254 ms 7032 KB Output is correct
23 Correct 750 ms 6624 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 9496 KB Output is correct
2 Correct 1091 ms 10072 KB Output is correct
3 Correct 1053 ms 10096 KB Output is correct
4 Correct 1087 ms 10048 KB Output is correct
5 Correct 1067 ms 10484 KB Output is correct
6 Correct 1550 ms 13300 KB Output is correct
7 Correct 1519 ms 13292 KB Output is correct
8 Correct 1545 ms 13288 KB Output is correct
9 Correct 36 ms 2436 KB Output is correct
10 Correct 856 ms 13576 KB Output is correct
11 Correct 794 ms 13300 KB Output is correct
12 Correct 965 ms 6612 KB Output is correct
13 Correct 967 ms 12772 KB Output is correct
14 Correct 786 ms 8828 KB Output is correct
15 Correct 550 ms 10688 KB Output is correct
16 Correct 925 ms 12844 KB Output is correct
17 Correct 777 ms 9380 KB Output is correct
18 Correct 38 ms 2452 KB Output is correct
19 Correct 871 ms 9412 KB Output is correct
20 Correct 713 ms 8836 KB Output is correct
21 Correct 648 ms 8760 KB Output is correct
22 Correct 535 ms 5436 KB Output is correct
23 Correct 503 ms 5324 KB Output is correct
24 Correct 567 ms 12476 KB Output is correct
25 Correct 509 ms 12480 KB Output is correct
26 Correct 996 ms 10392 KB Output is correct
27 Correct 1245 ms 13640 KB Output is correct
28 Correct 1076 ms 10040 KB Output is correct
29 Correct 798 ms 9384 KB Output is correct
30 Correct 1210 ms 13252 KB Output is correct
31 Correct 1228 ms 13256 KB Output is correct
32 Correct 1232 ms 13420 KB Output is correct
33 Correct 1077 ms 9880 KB Output is correct
34 Correct 1047 ms 9800 KB Output is correct
35 Correct 1070 ms 10020 KB Output is correct
36 Correct 838 ms 9424 KB Output is correct
37 Correct 837 ms 9436 KB Output is correct
38 Correct 832 ms 9328 KB Output is correct
39 Correct 711 ms 5968 KB Output is correct
40 Correct 709 ms 6048 KB Output is correct
41 Correct 705 ms 5984 KB Output is correct
42 Correct 693 ms 12240 KB Output is correct
43 Correct 695 ms 12140 KB Output is correct
44 Correct 682 ms 11952 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 26 ms 4692 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 10 ms 1748 KB Output is correct
6 Correct 9 ms 1624 KB Output is correct
7 Correct 10 ms 1688 KB Output is correct
8 Correct 10 ms 1740 KB Output is correct
9 Correct 13 ms 1652 KB Output is correct
10 Correct 12 ms 1748 KB Output is correct
11 Correct 11 ms 1748 KB Output is correct
12 Correct 13 ms 1672 KB Output is correct
13 Correct 16 ms 2412 KB Output is correct
14 Correct 14 ms 2260 KB Output is correct
15 Correct 13 ms 1748 KB Output is correct
16 Correct 11 ms 1620 KB Output is correct
17 Correct 11 ms 1668 KB Output is correct
18 Correct 1010 ms 9496 KB Output is correct
19 Correct 1091 ms 10072 KB Output is correct
20 Correct 1053 ms 10096 KB Output is correct
21 Correct 1087 ms 10048 KB Output is correct
22 Correct 1067 ms 10484 KB Output is correct
23 Correct 1550 ms 13300 KB Output is correct
24 Correct 1519 ms 13292 KB Output is correct
25 Correct 1545 ms 13288 KB Output is correct
26 Correct 36 ms 2436 KB Output is correct
27 Correct 856 ms 13576 KB Output is correct
28 Correct 794 ms 13300 KB Output is correct
29 Correct 965 ms 6612 KB Output is correct
30 Correct 967 ms 12772 KB Output is correct
31 Correct 786 ms 8828 KB Output is correct
32 Correct 550 ms 10688 KB Output is correct
33 Correct 925 ms 12844 KB Output is correct
34 Correct 777 ms 9380 KB Output is correct
35 Correct 38 ms 2452 KB Output is correct
36 Correct 871 ms 9412 KB Output is correct
37 Correct 713 ms 8836 KB Output is correct
38 Correct 648 ms 8760 KB Output is correct
39 Correct 535 ms 5436 KB Output is correct
40 Correct 503 ms 5324 KB Output is correct
41 Correct 567 ms 12476 KB Output is correct
42 Correct 509 ms 12480 KB Output is correct
43 Correct 1298 ms 6064 KB Output is correct
44 Correct 38 ms 2840 KB Output is correct
45 Correct 147 ms 4668 KB Output is correct
46 Correct 87 ms 4752 KB Output is correct
47 Correct 769 ms 6872 KB Output is correct
48 Correct 1306 ms 6856 KB Output is correct
49 Correct 771 ms 6776 KB Output is correct
50 Correct 643 ms 5308 KB Output is correct
51 Correct 620 ms 5468 KB Output is correct
52 Correct 634 ms 5412 KB Output is correct
53 Correct 985 ms 6116 KB Output is correct
54 Correct 971 ms 6044 KB Output is correct
55 Correct 983 ms 6288 KB Output is correct
56 Correct 741 ms 6928 KB Output is correct
57 Correct 756 ms 6956 KB Output is correct
58 Correct 1311 ms 6856 KB Output is correct
59 Correct 1330 ms 6940 KB Output is correct
60 Correct 1314 ms 6892 KB Output is correct
61 Correct 1312 ms 6792 KB Output is correct
62 Correct 1093 ms 6576 KB Output is correct
63 Correct 1092 ms 6612 KB Output is correct
64 Correct 1254 ms 7032 KB Output is correct
65 Correct 750 ms 6624 KB Output is correct
66 Correct 996 ms 10392 KB Output is correct
67 Correct 1245 ms 13640 KB Output is correct
68 Correct 1076 ms 10040 KB Output is correct
69 Correct 798 ms 9384 KB Output is correct
70 Correct 1210 ms 13252 KB Output is correct
71 Correct 1228 ms 13256 KB Output is correct
72 Correct 1232 ms 13420 KB Output is correct
73 Correct 1077 ms 9880 KB Output is correct
74 Correct 1047 ms 9800 KB Output is correct
75 Correct 1070 ms 10020 KB Output is correct
76 Correct 838 ms 9424 KB Output is correct
77 Correct 837 ms 9436 KB Output is correct
78 Correct 832 ms 9328 KB Output is correct
79 Correct 711 ms 5968 KB Output is correct
80 Correct 709 ms 6048 KB Output is correct
81 Correct 705 ms 5984 KB Output is correct
82 Correct 693 ms 12240 KB Output is correct
83 Correct 695 ms 12140 KB Output is correct
84 Correct 682 ms 11952 KB Output is correct
85 Correct 1630 ms 11488 KB Output is correct
86 Correct 182 ms 7840 KB Output is correct
87 Correct 125 ms 10308 KB Output is correct
88 Correct 1077 ms 15004 KB Output is correct
89 Correct 1611 ms 11852 KB Output is correct
90 Correct 1104 ms 15092 KB Output is correct
91 Correct 1109 ms 10400 KB Output is correct
92 Correct 1075 ms 10052 KB Output is correct
93 Correct 1528 ms 13048 KB Output is correct
94 Correct 1375 ms 11148 KB Output is correct
95 Correct 1361 ms 10936 KB Output is correct
96 Correct 1596 ms 14112 KB Output is correct
97 Correct 882 ms 7832 KB Output is correct
98 Correct 911 ms 14780 KB Output is correct
99 Correct 1683 ms 12048 KB Output is correct
100 Correct 1654 ms 11448 KB Output is correct
101 Correct 1675 ms 11824 KB Output is correct
102 Correct 1703 ms 11972 KB Output is correct
103 Correct 1782 ms 14560 KB Output is correct
104 Correct 1784 ms 14740 KB Output is correct
105 Correct 1401 ms 14164 KB Output is correct
106 Correct 1112 ms 13760 KB Output is correct
107 Correct 1277 ms 7720 KB Output is correct
108 Correct 1741 ms 12444 KB Output is correct
109 Correct 1243 ms 14384 KB Output is correct