oj.uz

답안 #571235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571235 2022-06-01T15:20:29 Z YouAreMyGalaxy 다리 (APIO19_bridges) C++17
100 / 100
 2766 ms 133492 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int block = 1000, M = 1e5, N = 5e4;
stack<tuple<int, int, int > > st;
int lab[N + 1], n, m, a[M + 1], b[M + 1], w[M + 1], t[M + 1], x[M + 1], y[M + 1], q, res[M + 1];
bitset<M + 1> changed;
vector<int> upt[M + 1];
int FindSet(int u)
{
    return lab[u] < 0 ? u : FindSet(lab[u]);
}
void Unite(int u, int v)
{
    u = FindSet(u);
    v = FindSet(v);
    if (u == v)
    {
        return ;
    }
    if (lab[u] > lab[v])
    {
        swap(u, v);
    }
    lab[u] += lab[v];
    st.push(make_tuple(u, v, lab[v]));
    lab[v] = u;
}
void roll_back(int sz)
{
    while(st.size() > sz)
    {
        int u, v, s;
        tie(u, v, s) = st.top();
        st.pop();
        lab[u] -= s;
        lab[v] = s;
    }
}
void read()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> a[i] >> b[i] >> w[i];
    }
    cin >> q;
    for (int i = 1; i <= q; ++ i)
    {
        cin >> t[i] >> x[i] >> y[i];
    }
}
void solve()
{
    for (int l = 1; l <= q; l+= block)
    {
        int r = min(q, l + block - 1);
        changed.reset();
        memset(lab, -1, sizeof(lab));
        while(!st.empty())
        {
            st.pop();
        }
        vector<int> tmp, query;
        for (int i = l; i <= r; ++ i)
        {
            if (t[i] == 1)
            {
                changed[x[i]] = true;
                tmp.push_back(x[i]);
            }
        }
        vector<int> unchanged;
        for (int i = 1; i <= m; ++ i)
        {
            if (!changed[i])
            {
                unchanged.push_back(i);
            }
        }
        sort(unchanged.begin(), unchanged.end(), [&](const int &a, const int &b)
             {
                 return w[a] < w[b];
             });
        for (int i = l; i <= r; ++ i)
        {
            if (t[i] == 1)
            {
                w[x[i]] = y[i];
                //tmp.push_back(i);
            }
            else
            {
                for (int j : tmp)
                {
                    if (w[j] >= y[i])
                    {
                        upt[i].push_back(j);
                    }
                }
                query.push_back(i);
            }
        }
        sort(query.begin(), query.end(), [&](const int & a, const int &b)
             {
                 return y[a] > y[b];
             });
        for (int i : query)
        {
            //cerr << i << '\n';
            while(!unchanged.empty() && w[unchanged.back()] >= y[i])
            {
                //cerr << unchanged.back() << ' ';
                Unite(a[unchanged.back()], b[unchanged.back()]);
                unchanged.pop_back();
            }
            //cerr << '\n';
            int sz = st.size();
            for (int j : upt[i])
            {
                Unite(a[j], b[j]);
                //cerr << j << ' ';
            }
            //cerr << '\n';
            res[i] = -lab[FindSet(x[i])];
            roll_back(sz);
            //cerr << '\n';
        }
    }
    for (int i = 1; i <= q; ++ i)
    {
        if (t[i] == 1)
        {
            continue;
        }
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message

bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:34:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     while(st.size() > sz)
      |           ~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2808 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 47 ms 9852 KB Output is correct
4 Correct 6 ms 3204 KB Output is correct
5 Correct 50 ms 10572 KB Output is correct
6 Correct 43 ms 10752 KB Output is correct
7 Correct 51 ms 10752 KB Output is correct
8 Correct 51 ms 9132 KB Output is correct
9 Correct 66 ms 15052 KB Output is correct
10 Correct 52 ms 10060 KB Output is correct
11 Correct 52 ms 9808 KB Output is correct
12 Correct 59 ms 12356 KB Output is correct
13 Correct 62 ms 10440 KB Output is correct
14 Correct 55 ms 9664 KB Output is correct
15 Correct 58 ms 10460 KB Output is correct
16 Correct 55 ms 13260 KB Output is correct
17 Correct 54 ms 12336 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1450 ms 75828 KB Output is correct
2 Correct 1525 ms 75612 KB Output is correct
3 Correct 1452 ms 75992 KB Output is correct
4 Correct 1537 ms 75512 KB Output is correct
5 Correct 1534 ms 76152 KB Output is correct
6 Correct 2177 ms 133492 KB Output is correct
7 Correct 2114 ms 130120 KB Output is correct
8 Correct 2149 ms 129840 KB Output is correct
9 Correct 52 ms 5920 KB Output is correct
10 Correct 1245 ms 100120 KB Output is correct
11 Correct 1173 ms 99496 KB Output is correct
12 Correct 1253 ms 55376 KB Output is correct
13 Correct 1349 ms 48620 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1187 ms 75168 KB Output is correct
2 Correct 980 ms 99508 KB Output is correct
3 Correct 1450 ms 102980 KB Output is correct
4 Correct 1151 ms 74780 KB Output is correct
5 Correct 40 ms 5968 KB Output is correct
6 Correct 1345 ms 94512 KB Output is correct
7 Correct 1110 ms 66768 KB Output is correct
8 Correct 918 ms 50784 KB Output is correct
9 Correct 792 ms 42656 KB Output is correct
10 Correct 732 ms 31056 KB Output is correct
11 Correct 801 ms 40228 KB Output is correct
12 Correct 728 ms 29796 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1784 ms 10804 KB Output is correct
2 Correct 60 ms 5952 KB Output is correct
3 Correct 178 ms 7136 KB Output is correct
4 Correct 107 ms 7092 KB Output is correct
5 Correct 938 ms 9368 KB Output is correct
6 Correct 1735 ms 11140 KB Output is correct
7 Correct 765 ms 9368 KB Output is correct
8 Correct 809 ms 8700 KB Output is correct
9 Correct 864 ms 8820 KB Output is correct
10 Correct 863 ms 8680 KB Output is correct
11 Correct 1317 ms 9700 KB Output is correct
12 Correct 1187 ms 9832 KB Output is correct
13 Correct 1268 ms 9668 KB Output is correct
14 Correct 851 ms 9448 KB Output is correct
15 Correct 855 ms 9340 KB Output is correct
16 Correct 1782 ms 10752 KB Output is correct
17 Correct 1754 ms 10696 KB Output is correct
18 Correct 1789 ms 10816 KB Output is correct
19 Correct 1741 ms 10824 KB Output is correct
20 Correct 1449 ms 9996 KB Output is correct
21 Correct 1483 ms 10000 KB Output is correct
22 Correct 1697 ms 10656 KB Output is correct
23 Correct 835 ms 9084 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1450 ms 75828 KB Output is correct
2 Correct 1525 ms 75612 KB Output is correct
3 Correct 1452 ms 75992 KB Output is correct
4 Correct 1537 ms 75512 KB Output is correct
5 Correct 1534 ms 76152 KB Output is correct
6 Correct 2177 ms 133492 KB Output is correct
7 Correct 2114 ms 130120 KB Output is correct
8 Correct 2149 ms 129840 KB Output is correct
9 Correct 52 ms 5920 KB Output is correct
10 Correct 1245 ms 100120 KB Output is correct
11 Correct 1173 ms 99496 KB Output is correct
12 Correct 1253 ms 55376 KB Output is correct
13 Correct 1349 ms 48620 KB Output is correct
14 Correct 1187 ms 75168 KB Output is correct
15 Correct 980 ms 99508 KB Output is correct
16 Correct 1450 ms 102980 KB Output is correct
17 Correct 1151 ms 74780 KB Output is correct
18 Correct 40 ms 5968 KB Output is correct
19 Correct 1345 ms 94512 KB Output is correct
20 Correct 1110 ms 66768 KB Output is correct
21 Correct 918 ms 50784 KB Output is correct
22 Correct 792 ms 42656 KB Output is correct
23 Correct 732 ms 31056 KB Output is correct
24 Correct 801 ms 40228 KB Output is correct
25 Correct 728 ms 29796 KB Output is correct
26 Correct 1367 ms 75800 KB Output is correct
27 Correct 1886 ms 104900 KB Output is correct
28 Correct 1643 ms 73920 KB Output is correct
29 Correct 1117 ms 31036 KB Output is correct
30 Correct 1754 ms 91288 KB Output is correct
31 Correct 1840 ms 93692 KB Output is correct
32 Correct 1741 ms 94248 KB Output is correct
33 Correct 1429 ms 74288 KB Output is correct
34 Correct 1531 ms 74464 KB Output is correct
35 Correct 1520 ms 74812 KB Output is correct
36 Correct 1165 ms 38040 KB Output is correct
37 Correct 1109 ms 36696 KB Output is correct
38 Correct 1161 ms 35160 KB Output is correct
39 Correct 963 ms 21208 KB Output is correct
40 Correct 964 ms 20408 KB Output is correct
41 Correct 950 ms 19888 KB Output is correct
42 Correct 966 ms 19532 KB Output is correct
43 Correct 956 ms 18876 KB Output is correct
44 Correct 974 ms 18412 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2808 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 47 ms 9852 KB Output is correct
4 Correct 6 ms 3204 KB Output is correct
5 Correct 50 ms 10572 KB Output is correct
6 Correct 43 ms 10752 KB Output is correct
7 Correct 51 ms 10752 KB Output is correct
8 Correct 51 ms 9132 KB Output is correct
9 Correct 66 ms 15052 KB Output is correct
10 Correct 52 ms 10060 KB Output is correct
11 Correct 52 ms 9808 KB Output is correct
12 Correct 59 ms 12356 KB Output is correct
13 Correct 62 ms 10440 KB Output is correct
14 Correct 55 ms 9664 KB Output is correct
15 Correct 58 ms 10460 KB Output is correct
16 Correct 55 ms 13260 KB Output is correct
17 Correct 54 ms 12336 KB Output is correct
18 Correct 1450 ms 75828 KB Output is correct
19 Correct 1525 ms 75612 KB Output is correct
20 Correct 1452 ms 75992 KB Output is correct
21 Correct 1537 ms 75512 KB Output is correct
22 Correct 1534 ms 76152 KB Output is correct
23 Correct 2177 ms 133492 KB Output is correct
24 Correct 2114 ms 130120 KB Output is correct
25 Correct 2149 ms 129840 KB Output is correct
26 Correct 52 ms 5920 KB Output is correct
27 Correct 1245 ms 100120 KB Output is correct
28 Correct 1173 ms 99496 KB Output is correct
29 Correct 1253 ms 55376 KB Output is correct
30 Correct 1349 ms 48620 KB Output is correct
31 Correct 1187 ms 75168 KB Output is correct
32 Correct 980 ms 99508 KB Output is correct
33 Correct 1450 ms 102980 KB Output is correct
34 Correct 1151 ms 74780 KB Output is correct
35 Correct 40 ms 5968 KB Output is correct
36 Correct 1345 ms 94512 KB Output is correct
37 Correct 1110 ms 66768 KB Output is correct
38 Correct 918 ms 50784 KB Output is correct
39 Correct 792 ms 42656 KB Output is correct
40 Correct 732 ms 31056 KB Output is correct
41 Correct 801 ms 40228 KB Output is correct
42 Correct 728 ms 29796 KB Output is correct
43 Correct 1784 ms 10804 KB Output is correct
44 Correct 60 ms 5952 KB Output is correct
45 Correct 178 ms 7136 KB Output is correct
46 Correct 107 ms 7092 KB Output is correct
47 Correct 938 ms 9368 KB Output is correct
48 Correct 1735 ms 11140 KB Output is correct
49 Correct 765 ms 9368 KB Output is correct
50 Correct 809 ms 8700 KB Output is correct
51 Correct 864 ms 8820 KB Output is correct
52 Correct 863 ms 8680 KB Output is correct
53 Correct 1317 ms 9700 KB Output is correct
54 Correct 1187 ms 9832 KB Output is correct
55 Correct 1268 ms 9668 KB Output is correct
56 Correct 851 ms 9448 KB Output is correct
57 Correct 855 ms 9340 KB Output is correct
58 Correct 1782 ms 10752 KB Output is correct
59 Correct 1754 ms 10696 KB Output is correct
60 Correct 1789 ms 10816 KB Output is correct
61 Correct 1741 ms 10824 KB Output is correct
62 Correct 1449 ms 9996 KB Output is correct
63 Correct 1483 ms 10000 KB Output is correct
64 Correct 1697 ms 10656 KB Output is correct
65 Correct 835 ms 9084 KB Output is correct
66 Correct 1367 ms 75800 KB Output is correct
67 Correct 1886 ms 104900 KB Output is correct
68 Correct 1643 ms 73920 KB Output is correct
69 Correct 1117 ms 31036 KB Output is correct
70 Correct 1754 ms 91288 KB Output is correct
71 Correct 1840 ms 93692 KB Output is correct
72 Correct 1741 ms 94248 KB Output is correct
73 Correct 1429 ms 74288 KB Output is correct
74 Correct 1531 ms 74464 KB Output is correct
75 Correct 1520 ms 74812 KB Output is correct
76 Correct 1165 ms 38040 KB Output is correct
77 Correct 1109 ms 36696 KB Output is correct
78 Correct 1161 ms 35160 KB Output is correct
79 Correct 963 ms 21208 KB Output is correct
80 Correct 964 ms 20408 KB Output is correct
81 Correct 950 ms 19888 KB Output is correct
82 Correct 966 ms 19532 KB Output is correct
83 Correct 956 ms 18876 KB Output is correct
84 Correct 974 ms 18412 KB Output is correct
85 Correct 2557 ms 77776 KB Output is correct
86 Correct 275 ms 13196 KB Output is correct
87 Correct 172 ms 17620 KB Output is correct
88 Correct 1566 ms 89792 KB Output is correct
89 Correct 2179 ms 76300 KB Output is correct
90 Correct 1766 ms 98080 KB Output is correct
91 Correct 1748 ms 75664 KB Output is correct
92 Correct 1597 ms 75528 KB Output is correct
93 Correct 2306 ms 113316 KB Output is correct
94 Correct 1953 ms 76648 KB Output is correct
95 Correct 2077 ms 76756 KB Output is correct
96 Correct 2609 ms 117432 KB Output is correct
97 Correct 1191 ms 42508 KB Output is correct
98 Correct 1285 ms 39104 KB Output is correct
99 Correct 2574 ms 78784 KB Output is correct
100 Correct 2671 ms 77504 KB Output is correct
101 Correct 2425 ms 77576 KB Output is correct
102 Correct 2627 ms 77636 KB Output is correct
103 Correct 2766 ms 122772 KB Output is correct
104 Correct 2545 ms 122160 KB Output is correct
105 Correct 1793 ms 49968 KB Output is correct
106 Correct 1400 ms 29872 KB Output is correct
107 Correct 1753 ms 56688 KB Output is correct
108 Correct 2302 ms 112904 KB Output is correct
109 Correct 1574 ms 116292 KB Output is correct