oj.uz

Submission #933894

# Submission time Handle Problem Language Result Execution time Memory
933894 2024-02-26T14:08:04 Z Hanksburger Bridges (APIO19_bridges) C++17
100 / 100
 1885 ms 17420 KB 
#include <bits/stdc++.h>
using namespace std;
int U[100005], V[100005], W[100005], t[100005], x[100005], y[100005], ans[100005], par[50005], sz[50005];
vector<pair<pair<int, int>, pair<int, int> > > update;
vector<int> changed[100005];
void add(int u, int v, int ok)
{
    while (par[u]!=u)
        u=par[u];
    while (par[v]!=v)
        v=par[v];
    if (u==v)
        return;
    if (ok)
        update.push_back({{u, v}, {sz[u], sz[v]}});
    if (sz[u]<sz[v])
    {
        par[u]=v;
        sz[v]+=sz[u];
    }
    else
    {
        par[v]=u;
        sz[u]+=sz[v];
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m;
    for (int i=1; i<=m; i++)
        cin >> U[i] >> V[i] >> W[i];
    cin >> q;
    for (int i=1; i<=q; i++)
        cin >> t[i] >> x[i] >> y[i];
    for (int i=1; i<=q; i+=1000)
    {
        int l=i, r=min(i+999, q);
        for (int j=1; j<=m; j++)
            changed[j].clear();
        for (int j=l; j<=r; j++)
            if (t[j]==1)
                changed[x[j]].push_back(j);
        vector<pair<int, pair<int, int> > > vec1;
        vector<pair<int, int> > vec0[1005];
        for (int j=1; j<=m; j++)
        {
            if (changed[j].empty())
                vec1.push_back({W[j], {U[j], V[j]}});
            else
            {
                for (int k=l; k<changed[j][0]; k++)
                    if (t[k]==2 && y[k]<=W[j])
                    {
                        vec0[k-l].push_back({U[j], V[j]});
                    //    cout << "add " << k-l << ' ' << U[j] << ' ' << V[j] << '\n';
                    }
                int cnt=changed[j].size();
                for (int k=0; k<=cnt-2; k++)
                    for (int kk=changed[j][k]+1; kk<changed[j][k+1]; kk++)
                    {
                        if (t[kk]==2 && y[kk]<=y[changed[j][k]])
                        {
                            vec0[kk-l].push_back({U[j], V[j]});
                        //    cout << "add " << kk-l << ' ' << U[j] << ' ' << V[j] << '\n';
                        }
                    }
                for (int k=changed[j][cnt-1]; k<=r; k++)
                    if (t[k]==2 && y[k]<=y[changed[j][cnt-1]])
                    {
                        vec0[k-l].push_back({U[j], V[j]});
                    //    cout << "add " << k-l << ' ' << U[j] << ' ' << V[j] << '\n';
                    }
                W[j]=y[changed[j][cnt-1]];
            }
        }
        vector<pair<int, pair<int, int> > > qry;
        for (int j=0; j<vec1.size(); j++)
            qry.push_back({vec1[j].first, {1, j}});
        for (int j=l; j<=r; j++)
            if (t[j]==2)
                qry.push_back({y[j], {0, j}});
        sort(qry.begin(), qry.end());
        for (int j=1; j<=n; j++)
            par[j]=j, sz[j]=1;
        for (int j=qry.size()-1; j>=0; j--)
        {
        //    cout << "qry " << j << ' ' << qry[j].second.first << ' ' << qry[j].second.second << '\n';
            int ind=qry[j].second.second;
            if (qry[j].second.first)
                add(vec1[ind].second.first, vec1[ind].second.second, 0);
            else
            {
                for (int k=0; k<vec0[ind-l].size(); k++)
                    add(vec0[ind-l][k].first, vec0[ind-l][k].second, 1);
                int cur=x[ind];
                while (par[cur]!=cur)
                    cur=par[cur];
                ans[ind]=sz[cur];
                for (int k=update.size()-1; k>=0; k--)
                {
                    par[update[k].first.first]=update[k].first.first;
                    par[update[k].first.second]=update[k].first.second;
                    sz[update[k].first.first]=update[k].second.first;
                    sz[update[k].first.second]=update[k].second.second;
                }
                update.clear();
            /*    cout << "par: ";
                for (int k=1; k<=n; k++)
                    cout << par[k] << ' ';
                cout << '\n';
                cout << "size: ";
                for (int k=1; k<=n; k++)
                    cout << sz[k] << ' ';
                cout << '\n'; */
            }
        }
    }
    for (int i=1; i<=q; i++)
        if (t[i]==2)
            cout << ans[i] << '\n';
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:81:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int j=0; j<vec1.size(); j++)
      |                       ~^~~~~~~~~~~~
bridges.cpp:97:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |                 for (int k=0; k<vec0[ind-l].size(); k++)
      |                               ~^~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 35 ms 6316 KB Output is correct
4 Correct 4 ms 4784 KB Output is correct
5 Correct 14 ms 5368 KB Output is correct
6 Correct 15 ms 5208 KB Output is correct
7 Correct 14 ms 5212 KB Output is correct
8 Correct 16 ms 5212 KB Output is correct
9 Correct 17 ms 5212 KB Output is correct
10 Correct 15 ms 5212 KB Output is correct
11 Correct 14 ms 5212 KB Output is correct
12 Correct 17 ms 5412 KB Output is correct
13 Correct 21 ms 5392 KB Output is correct
14 Correct 18 ms 5468 KB Output is correct
15 Correct 16 ms 5296 KB Output is correct
16 Correct 16 ms 5212 KB Output is correct
17 Correct 16 ms 5208 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 12976 KB Output is correct
2 Correct 1082 ms 12812 KB Output is correct
3 Correct 1102 ms 12636 KB Output is correct
4 Correct 1096 ms 12688 KB Output is correct
5 Correct 1059 ms 12820 KB Output is correct
6 Correct 1212 ms 15208 KB Output is correct
7 Correct 1262 ms 14640 KB Output is correct
8 Correct 1208 ms 14712 KB Output is correct
9 Correct 28 ms 6228 KB Output is correct
10 Correct 1008 ms 13104 KB Output is correct
11 Correct 1024 ms 12284 KB Output is correct
12 Correct 865 ms 11392 KB Output is correct
13 Correct 863 ms 12224 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 11492 KB Output is correct
2 Correct 548 ms 9908 KB Output is correct
3 Correct 855 ms 12264 KB Output is correct
4 Correct 775 ms 11412 KB Output is correct
5 Correct 27 ms 6224 KB Output is correct
6 Correct 892 ms 11900 KB Output is correct
7 Correct 729 ms 11228 KB Output is correct
8 Correct 666 ms 10780 KB Output is correct
9 Correct 588 ms 10316 KB Output is correct
10 Correct 541 ms 10008 KB Output is correct
11 Correct 593 ms 10412 KB Output is correct
12 Correct 554 ms 10228 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 14016 KB Output is correct
2 Correct 26 ms 6228 KB Output is correct
3 Correct 146 ms 11616 KB Output is correct
4 Correct 194 ms 11844 KB Output is correct
5 Correct 1489 ms 12416 KB Output is correct
6 Correct 1317 ms 13840 KB Output is correct
7 Correct 1472 ms 12312 KB Output is correct
8 Correct 636 ms 10288 KB Output is correct
9 Correct 645 ms 10352 KB Output is correct
10 Correct 649 ms 10092 KB Output is correct
11 Correct 1024 ms 12372 KB Output is correct
12 Correct 1025 ms 12468 KB Output is correct
13 Correct 1029 ms 12104 KB Output is correct
14 Correct 1367 ms 12136 KB Output is correct
15 Correct 1413 ms 12664 KB Output is correct
16 Correct 1337 ms 13852 KB Output is correct
17 Correct 1370 ms 13820 KB Output is correct
18 Correct 1334 ms 14052 KB Output is correct
19 Correct 1371 ms 14240 KB Output is correct
20 Correct 1165 ms 12588 KB Output is correct
21 Correct 1202 ms 12480 KB Output is correct
22 Correct 1391 ms 13284 KB Output is correct
23 Correct 1346 ms 11368 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 12976 KB Output is correct
2 Correct 1082 ms 12812 KB Output is correct
3 Correct 1102 ms 12636 KB Output is correct
4 Correct 1096 ms 12688 KB Output is correct
5 Correct 1059 ms 12820 KB Output is correct
6 Correct 1212 ms 15208 KB Output is correct
7 Correct 1262 ms 14640 KB Output is correct
8 Correct 1208 ms 14712 KB Output is correct
9 Correct 28 ms 6228 KB Output is correct
10 Correct 1008 ms 13104 KB Output is correct
11 Correct 1024 ms 12284 KB Output is correct
12 Correct 865 ms 11392 KB Output is correct
13 Correct 863 ms 12224 KB Output is correct
14 Correct 789 ms 11492 KB Output is correct
15 Correct 548 ms 9908 KB Output is correct
16 Correct 855 ms 12264 KB Output is correct
17 Correct 775 ms 11412 KB Output is correct
18 Correct 27 ms 6224 KB Output is correct
19 Correct 892 ms 11900 KB Output is correct
20 Correct 729 ms 11228 KB Output is correct
21 Correct 666 ms 10780 KB Output is correct
22 Correct 588 ms 10316 KB Output is correct
23 Correct 541 ms 10008 KB Output is correct
24 Correct 593 ms 10412 KB Output is correct
25 Correct 554 ms 10228 KB Output is correct
26 Correct 1052 ms 12816 KB Output is correct
27 Correct 1177 ms 13916 KB Output is correct
28 Correct 1122 ms 12556 KB Output is correct
29 Correct 942 ms 11928 KB Output is correct
30 Correct 1129 ms 13092 KB Output is correct
31 Correct 1126 ms 13244 KB Output is correct
32 Correct 1168 ms 13116 KB Output is correct
33 Correct 1097 ms 12908 KB Output is correct
34 Correct 1099 ms 12768 KB Output is correct
35 Correct 1093 ms 12588 KB Output is correct
36 Correct 924 ms 11752 KB Output is correct
37 Correct 888 ms 11772 KB Output is correct
38 Correct 952 ms 12192 KB Output is correct
39 Correct 721 ms 11152 KB Output is correct
40 Correct 712 ms 11040 KB Output is correct
41 Correct 720 ms 10924 KB Output is correct
42 Correct 770 ms 11768 KB Output is correct
43 Correct 759 ms 11728 KB Output is correct
44 Correct 794 ms 11756 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 35 ms 6316 KB Output is correct
4 Correct 4 ms 4784 KB Output is correct
5 Correct 14 ms 5368 KB Output is correct
6 Correct 15 ms 5208 KB Output is correct
7 Correct 14 ms 5212 KB Output is correct
8 Correct 16 ms 5212 KB Output is correct
9 Correct 17 ms 5212 KB Output is correct
10 Correct 15 ms 5212 KB Output is correct
11 Correct 14 ms 5212 KB Output is correct
12 Correct 17 ms 5412 KB Output is correct
13 Correct 21 ms 5392 KB Output is correct
14 Correct 18 ms 5468 KB Output is correct
15 Correct 16 ms 5296 KB Output is correct
16 Correct 16 ms 5212 KB Output is correct
17 Correct 16 ms 5208 KB Output is correct
18 Correct 1065 ms 12976 KB Output is correct
19 Correct 1082 ms 12812 KB Output is correct
20 Correct 1102 ms 12636 KB Output is correct
21 Correct 1096 ms 12688 KB Output is correct
22 Correct 1059 ms 12820 KB Output is correct
23 Correct 1212 ms 15208 KB Output is correct
24 Correct 1262 ms 14640 KB Output is correct
25 Correct 1208 ms 14712 KB Output is correct
26 Correct 28 ms 6228 KB Output is correct
27 Correct 1008 ms 13104 KB Output is correct
28 Correct 1024 ms 12284 KB Output is correct
29 Correct 865 ms 11392 KB Output is correct
30 Correct 863 ms 12224 KB Output is correct
31 Correct 789 ms 11492 KB Output is correct
32 Correct 548 ms 9908 KB Output is correct
33 Correct 855 ms 12264 KB Output is correct
34 Correct 775 ms 11412 KB Output is correct
35 Correct 27 ms 6224 KB Output is correct
36 Correct 892 ms 11900 KB Output is correct
37 Correct 729 ms 11228 KB Output is correct
38 Correct 666 ms 10780 KB Output is correct
39 Correct 588 ms 10316 KB Output is correct
40 Correct 541 ms 10008 KB Output is correct
41 Correct 593 ms 10412 KB Output is correct
42 Correct 554 ms 10228 KB Output is correct
43 Correct 1345 ms 14016 KB Output is correct
44 Correct 26 ms 6228 KB Output is correct
45 Correct 146 ms 11616 KB Output is correct
46 Correct 194 ms 11844 KB Output is correct
47 Correct 1489 ms 12416 KB Output is correct
48 Correct 1317 ms 13840 KB Output is correct
49 Correct 1472 ms 12312 KB Output is correct
50 Correct 636 ms 10288 KB Output is correct
51 Correct 645 ms 10352 KB Output is correct
52 Correct 649 ms 10092 KB Output is correct
53 Correct 1024 ms 12372 KB Output is correct
54 Correct 1025 ms 12468 KB Output is correct
55 Correct 1029 ms 12104 KB Output is correct
56 Correct 1367 ms 12136 KB Output is correct
57 Correct 1413 ms 12664 KB Output is correct
58 Correct 1337 ms 13852 KB Output is correct
59 Correct 1370 ms 13820 KB Output is correct
60 Correct 1334 ms 14052 KB Output is correct
61 Correct 1371 ms 14240 KB Output is correct
62 Correct 1165 ms 12588 KB Output is correct
63 Correct 1202 ms 12480 KB Output is correct
64 Correct 1391 ms 13284 KB Output is correct
65 Correct 1346 ms 11368 KB Output is correct
66 Correct 1052 ms 12816 KB Output is correct
67 Correct 1177 ms 13916 KB Output is correct
68 Correct 1122 ms 12556 KB Output is correct
69 Correct 942 ms 11928 KB Output is correct
70 Correct 1129 ms 13092 KB Output is correct
71 Correct 1126 ms 13244 KB Output is correct
72 Correct 1168 ms 13116 KB Output is correct
73 Correct 1097 ms 12908 KB Output is correct
74 Correct 1099 ms 12768 KB Output is correct
75 Correct 1093 ms 12588 KB Output is correct
76 Correct 924 ms 11752 KB Output is correct
77 Correct 888 ms 11772 KB Output is correct
78 Correct 952 ms 12192 KB Output is correct
79 Correct 721 ms 11152 KB Output is correct
80 Correct 712 ms 11040 KB Output is correct
81 Correct 720 ms 10924 KB Output is correct
82 Correct 770 ms 11768 KB Output is correct
83 Correct 759 ms 11728 KB Output is correct
84 Correct 794 ms 11756 KB Output is correct
85 Correct 1826 ms 16600 KB Output is correct
86 Correct 189 ms 13424 KB Output is correct
87 Correct 250 ms 15644 KB Output is correct
88 Correct 1880 ms 15572 KB Output is correct
89 Correct 1833 ms 16704 KB Output is correct
90 Correct 1872 ms 15324 KB Output is correct
91 Correct 1063 ms 12724 KB Output is correct
92 Correct 1105 ms 12720 KB Output is correct
93 Correct 1303 ms 13672 KB Output is correct
94 Correct 1548 ms 15268 KB Output is correct
95 Correct 1448 ms 15264 KB Output is correct
96 Correct 1612 ms 16148 KB Output is correct
97 Correct 1667 ms 13840 KB Output is correct
98 Correct 1605 ms 15052 KB Output is correct
99 Correct 1811 ms 16564 KB Output is correct
100 Correct 1803 ms 16540 KB Output is correct
101 Correct 1885 ms 16884 KB Output is correct
102 Correct 1790 ms 16744 KB Output is correct
103 Correct 1816 ms 17420 KB Output is correct
104 Correct 1706 ms 17212 KB Output is correct
105 Correct 1383 ms 15280 KB Output is correct
106 Correct 1229 ms 14436 KB Output is correct
107 Correct 1366 ms 14696 KB Output is correct
108 Correct 1873 ms 17008 KB Output is correct
109 Correct 1844 ms 14896 KB Output is correct