oj.uz

Submission #972589

# Submission time Handle Problem Language Result Execution time Memory
972589 2024-04-30T16:37:22 Z simona1230 Bridges (APIO19_bridges) C++17
100 / 100
 2183 ms 252552 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n,m;
pair<int,int> e[100001];
int w[100001];
int q;
int t[100001],a[100001],b[100001];
void read()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        w[i]=c;
        e[i]={x,y};
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>t[i]>>a[i]>>b[i];
    }
}
const int block=1000;

int used[100001];
vector<int> unch,qr,upd[100001];

bool cmp1(int x,int y)
{
    return w[x]>w[y];
}
bool cmp2(int x,int y)
{
    return b[x]>b[y];
}

struct rolling
{
    int x,szx,y,szy,rnkx,rnky;
    rolling(){}
    rolling(int _x,int _szx,int rx,int _y,int _szy,int ry)
    {
        x=_x;
        szx=_szx;
        y=_y;
        szy=_szy;

        rnkx=rx;
        rnky=ry;
    }
};
stack<rolling> s;
int ans[100001],rnk[100001],par[100001],sz[100001];

void init()
{
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        rnk[i]=0;
        par[i]=i;
    }
}

int find_parent(int x)
{
    if(x==par[x])return x;
    return find_parent(par[x]);
}

void unite(int idx)// idx is the index of the edge in e[]
{
    int i=e[idx].first;
    int j=e[idx].second;
    i=find_parent(i);
    j=find_parent(j);

    if(i!=j)
    {
        if(rnk[i]>rnk[j])
            swap(i,j);
        s.push({i,sz[i],rnk[i],j,sz[j],rnk[j]});
        par[i]=j;
        sz[j]+=sz[i];
        if(rnk[j]==rnk[i])
            rnk[j]++;
    }
}

void rollback(int prsz)
{
    while(s.size()!=prsz)
    {
        rolling r=s.top();
        s.pop();

        par[r.x]=r.x;
        sz[r.x]=r.szx;
        par[r.y]=r.y;
        sz[r.y]=r.szy;
    }
}

void solve()
{
    for(int l=1;l<=q;l+=block)
    {
        init();
        unch.clear();// the unchanged edges' indexes
        qr.clear();// the indexes of the queries in the original order
        int r=l+block-1;

        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
                used[a[i]]=l;
        }

        for(int i=1;i<=m;i++)
        {
            if(used[i]!=l)
                unch.push_back(i);
        }
        sort(unch.begin(),unch.end(),cmp1);

        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
                w[a[i]]=b[i];

            if(t[i]==2)
            {
                qr.push_back(i);
                for(int j=l;j<=r;j++)
                    if(t[j]==1&&w[a[j]]>=b[i])
                        upd[i].push_back(a[j]);
            }
        }
        // sort queries by weight of car big to small, then add edges >=
        // from the unchanged ones and the updates
        // afterwards rollback to before the updates and go on

        sort(qr.begin(),qr.end(),cmp2);

        int j=0;
        for(int i=0;i<qr.size();i++)
        {
            int lim=b[qr[i]];
            while(j<unch.size()&&w[unch[j]]>=lim)
            {
                unite(unch[j]);
                j++;
            }

            int prsz=s.size();
            for(int j=0;j<upd[qr[i]].size();j++)
                unite(upd[qr[i]][j]);

            ans[qr[i]]=sz[find_parent(a[qr[i]])];

            rollback(prsz);
        }
    }

    for(int i=1;i<=q;i++)
        if(t[i]==2)
            cout<<ans[i]<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	return 0;
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:95:19: warning: comparison of integer expressions of different signedness: 'std::stack<rolling>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     while(s.size()!=prsz)
      |           ~~~~~~~~^~~~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int i=0;i<qr.size();i++)
      |                     ~^~~~~~~~~~
bridges.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             while(j<unch.size()&&w[unch[j]]>=lim)
      |                   ~^~~~~~~~~~~~
bridges.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int j=0;j<upd[qr[i]].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 40 ms 13132 KB Output is correct
4 Correct 10 ms 6492 KB Output is correct
5 Correct 48 ms 13808 KB Output is correct
6 Correct 33 ms 14200 KB Output is correct
7 Correct 39 ms 14416 KB Output is correct
8 Correct 50 ms 12564 KB Output is correct
9 Correct 48 ms 18524 KB Output is correct
10 Correct 48 ms 13464 KB Output is correct
11 Correct 48 ms 13136 KB Output is correct
12 Correct 56 ms 15648 KB Output is correct
13 Correct 55 ms 13648 KB Output is correct
14 Correct 53 ms 13036 KB Output is correct
15 Correct 55 ms 13652 KB Output is correct
16 Correct 40 ms 16720 KB Output is correct
17 Correct 43 ms 15700 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 195788 KB Output is correct
2 Correct 1377 ms 195984 KB Output is correct
3 Correct 1379 ms 194656 KB Output is correct
4 Correct 1390 ms 195756 KB Output is correct
5 Correct 1399 ms 196376 KB Output is correct
6 Correct 1574 ms 252552 KB Output is correct
7 Correct 1541 ms 250720 KB Output is correct
8 Correct 1566 ms 248572 KB Output is correct
9 Correct 104 ms 6620 KB Output is correct
10 Correct 930 ms 223332 KB Output is correct
11 Correct 872 ms 222188 KB Output is correct
12 Correct 1145 ms 177280 KB Output is correct
13 Correct 1140 ms 169264 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 153184 KB Output is correct
2 Correct 752 ms 118492 KB Output is correct
3 Correct 1210 ms 181472 KB Output is correct
4 Correct 1096 ms 152648 KB Output is correct
5 Correct 89 ms 6600 KB Output is correct
6 Correct 1212 ms 171592 KB Output is correct
7 Correct 1020 ms 143896 KB Output is correct
8 Correct 907 ms 127916 KB Output is correct
9 Correct 747 ms 121812 KB Output is correct
10 Correct 766 ms 109348 KB Output is correct
11 Correct 766 ms 116088 KB Output is correct
12 Correct 662 ms 105016 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1641 ms 129016 KB Output is correct
2 Correct 90 ms 6600 KB Output is correct
3 Correct 167 ms 7572 KB Output is correct
4 Correct 86 ms 7520 KB Output is correct
5 Correct 948 ms 127572 KB Output is correct
6 Correct 1638 ms 129048 KB Output is correct
7 Correct 925 ms 127512 KB Output is correct
8 Correct 839 ms 128544 KB Output is correct
9 Correct 851 ms 128308 KB Output is correct
10 Correct 866 ms 128708 KB Output is correct
11 Correct 1248 ms 130676 KB Output is correct
12 Correct 1270 ms 129128 KB Output is correct
13 Correct 1265 ms 128992 KB Output is correct
14 Correct 871 ms 127104 KB Output is correct
15 Correct 954 ms 127048 KB Output is correct
16 Correct 1650 ms 128592 KB Output is correct
17 Correct 1719 ms 130576 KB Output is correct
18 Correct 1675 ms 131056 KB Output is correct
19 Correct 1778 ms 129136 KB Output is correct
20 Correct 1402 ms 131100 KB Output is correct
21 Correct 1449 ms 131124 KB Output is correct
22 Correct 1629 ms 128200 KB Output is correct
23 Correct 960 ms 116972 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 195788 KB Output is correct
2 Correct 1377 ms 195984 KB Output is correct
3 Correct 1379 ms 194656 KB Output is correct
4 Correct 1390 ms 195756 KB Output is correct
5 Correct 1399 ms 196376 KB Output is correct
6 Correct 1574 ms 252552 KB Output is correct
7 Correct 1541 ms 250720 KB Output is correct
8 Correct 1566 ms 248572 KB Output is correct
9 Correct 104 ms 6620 KB Output is correct
10 Correct 930 ms 223332 KB Output is correct
11 Correct 872 ms 222188 KB Output is correct
12 Correct 1145 ms 177280 KB Output is correct
13 Correct 1140 ms 169264 KB Output is correct
14 Correct 1142 ms 153184 KB Output is correct
15 Correct 752 ms 118492 KB Output is correct
16 Correct 1210 ms 181472 KB Output is correct
17 Correct 1096 ms 152648 KB Output is correct
18 Correct 89 ms 6600 KB Output is correct
19 Correct 1212 ms 171592 KB Output is correct
20 Correct 1020 ms 143896 KB Output is correct
21 Correct 907 ms 127916 KB Output is correct
22 Correct 747 ms 121812 KB Output is correct
23 Correct 766 ms 109348 KB Output is correct
24 Correct 766 ms 116088 KB Output is correct
25 Correct 662 ms 105016 KB Output is correct
26 Correct 1467 ms 198656 KB Output is correct
27 Correct 1537 ms 228196 KB Output is correct
28 Correct 1427 ms 195132 KB Output is correct
29 Correct 1104 ms 153624 KB Output is correct
30 Correct 1504 ms 212836 KB Output is correct
31 Correct 1510 ms 217184 KB Output is correct
32 Correct 1528 ms 215580 KB Output is correct
33 Correct 1412 ms 197820 KB Output is correct
34 Correct 1391 ms 197404 KB Output is correct
35 Correct 1448 ms 195696 KB Output is correct
36 Correct 1125 ms 158788 KB Output is correct
37 Correct 1142 ms 159420 KB Output is correct
38 Correct 1140 ms 157732 KB Output is correct
39 Correct 938 ms 144840 KB Output is correct
40 Correct 960 ms 144304 KB Output is correct
41 Correct 931 ms 141664 KB Output is correct
42 Correct 876 ms 136368 KB Output is correct
43 Correct 860 ms 135600 KB Output is correct
44 Correct 835 ms 136648 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 40 ms 13132 KB Output is correct
4 Correct 10 ms 6492 KB Output is correct
5 Correct 48 ms 13808 KB Output is correct
6 Correct 33 ms 14200 KB Output is correct
7 Correct 39 ms 14416 KB Output is correct
8 Correct 50 ms 12564 KB Output is correct
9 Correct 48 ms 18524 KB Output is correct
10 Correct 48 ms 13464 KB Output is correct
11 Correct 48 ms 13136 KB Output is correct
12 Correct 56 ms 15648 KB Output is correct
13 Correct 55 ms 13648 KB Output is correct
14 Correct 53 ms 13036 KB Output is correct
15 Correct 55 ms 13652 KB Output is correct
16 Correct 40 ms 16720 KB Output is correct
17 Correct 43 ms 15700 KB Output is correct
18 Correct 1345 ms 195788 KB Output is correct
19 Correct 1377 ms 195984 KB Output is correct
20 Correct 1379 ms 194656 KB Output is correct
21 Correct 1390 ms 195756 KB Output is correct
22 Correct 1399 ms 196376 KB Output is correct
23 Correct 1574 ms 252552 KB Output is correct
24 Correct 1541 ms 250720 KB Output is correct
25 Correct 1566 ms 248572 KB Output is correct
26 Correct 104 ms 6620 KB Output is correct
27 Correct 930 ms 223332 KB Output is correct
28 Correct 872 ms 222188 KB Output is correct
29 Correct 1145 ms 177280 KB Output is correct
30 Correct 1140 ms 169264 KB Output is correct
31 Correct 1142 ms 153184 KB Output is correct
32 Correct 752 ms 118492 KB Output is correct
33 Correct 1210 ms 181472 KB Output is correct
34 Correct 1096 ms 152648 KB Output is correct
35 Correct 89 ms 6600 KB Output is correct
36 Correct 1212 ms 171592 KB Output is correct
37 Correct 1020 ms 143896 KB Output is correct
38 Correct 907 ms 127916 KB Output is correct
39 Correct 747 ms 121812 KB Output is correct
40 Correct 766 ms 109348 KB Output is correct
41 Correct 766 ms 116088 KB Output is correct
42 Correct 662 ms 105016 KB Output is correct
43 Correct 1641 ms 129016 KB Output is correct
44 Correct 90 ms 6600 KB Output is correct
45 Correct 167 ms 7572 KB Output is correct
46 Correct 86 ms 7520 KB Output is correct
47 Correct 948 ms 127572 KB Output is correct
48 Correct 1638 ms 129048 KB Output is correct
49 Correct 925 ms 127512 KB Output is correct
50 Correct 839 ms 128544 KB Output is correct
51 Correct 851 ms 128308 KB Output is correct
52 Correct 866 ms 128708 KB Output is correct
53 Correct 1248 ms 130676 KB Output is correct
54 Correct 1270 ms 129128 KB Output is correct
55 Correct 1265 ms 128992 KB Output is correct
56 Correct 871 ms 127104 KB Output is correct
57 Correct 954 ms 127048 KB Output is correct
58 Correct 1650 ms 128592 KB Output is correct
59 Correct 1719 ms 130576 KB Output is correct
60 Correct 1675 ms 131056 KB Output is correct
61 Correct 1778 ms 129136 KB Output is correct
62 Correct 1402 ms 131100 KB Output is correct
63 Correct 1449 ms 131124 KB Output is correct
64 Correct 1629 ms 128200 KB Output is correct
65 Correct 960 ms 116972 KB Output is correct
66 Correct 1467 ms 198656 KB Output is correct
67 Correct 1537 ms 228196 KB Output is correct
68 Correct 1427 ms 195132 KB Output is correct
69 Correct 1104 ms 153624 KB Output is correct
70 Correct 1504 ms 212836 KB Output is correct
71 Correct 1510 ms 217184 KB Output is correct
72 Correct 1528 ms 215580 KB Output is correct
73 Correct 1412 ms 197820 KB Output is correct
74 Correct 1391 ms 197404 KB Output is correct
75 Correct 1448 ms 195696 KB Output is correct
76 Correct 1125 ms 158788 KB Output is correct
77 Correct 1142 ms 159420 KB Output is correct
78 Correct 1140 ms 157732 KB Output is correct
79 Correct 938 ms 144840 KB Output is correct
80 Correct 960 ms 144304 KB Output is correct
81 Correct 931 ms 141664 KB Output is correct
82 Correct 876 ms 136368 KB Output is correct
83 Correct 860 ms 135600 KB Output is correct
84 Correct 835 ms 136648 KB Output is correct
85 Correct 2072 ms 197932 KB Output is correct
86 Correct 202 ms 15920 KB Output is correct
87 Correct 109 ms 20432 KB Output is correct
88 Correct 1226 ms 209720 KB Output is correct
89 Correct 2021 ms 198292 KB Output is correct
90 Correct 1237 ms 219976 KB Output is correct
91 Correct 1425 ms 197120 KB Output is correct
92 Correct 1407 ms 196724 KB Output is correct
93 Correct 1727 ms 236600 KB Output is correct
94 Correct 1706 ms 199424 KB Output is correct
95 Correct 1710 ms 200892 KB Output is correct
96 Correct 1687 ms 239620 KB Output is correct
97 Correct 1075 ms 164404 KB Output is correct
98 Correct 1056 ms 160880 KB Output is correct
99 Correct 2045 ms 200512 KB Output is correct
100 Correct 2099 ms 200916 KB Output is correct
101 Correct 2183 ms 201620 KB Output is correct
102 Correct 2112 ms 201544 KB Output is correct
103 Correct 1855 ms 244884 KB Output is correct
104 Correct 1851 ms 246376 KB Output is correct
105 Correct 1541 ms 172368 KB Output is correct
106 Correct 1269 ms 153996 KB Output is correct
107 Correct 1552 ms 180860 KB Output is correct
108 Correct 1937 ms 231900 KB Output is correct
109 Correct 1382 ms 225612 KB Output is correct