oj.uz

답안 #660226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660226 2022-11-21T08:35:21 Z bojackduy 다리 (APIO19_bridges) C++14
100 / 100
 2007 ms 42752 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#define task ""
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (y < x) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}

const int N = 1e6 + 1;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;

int n, m, q;
int u[N], v[N], w[N], t[N], id[N], z[N], lab[N], ans[N];
vi b[N];
bool changed[N];
stack<array<int, 3>> st;
int root(int u) {
    return (lab[u] < 0 ? u : root(lab[u]));
}
bool join(int u, int v) {
    if ((u = root(u)) == (v = root(v))) return 0;
    if (lab[u] > lab[v]) swap(u, v);
    st.push({u, v, lab[v]});
    lab[u] += lab[v];
    lab[v] = u;
return 1;
}
void roll_back(int sz) {
    while (st.size() > sz) {
        int u = st.top()[0];
        int v = st.top()[1];
        int w = st.top()[2];
        st.pop();
        lab[u] -= w;
        lab[v] = w;
    }
}
void solve(int test = -1) {
    memset(lab, -1, sizeof lab);
    memset(ans, -1, sizeof ans);
    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] >> id[i] >> z[i];
    }
    int blsz = 1000;
    for (int l = 1; l <= q; l += blsz) {
        int r = min(q, l + blsz - 1);
        
        vi calc, upd, unchanged;
        for (int i = l; i <= r; i++) {
            if (t[i] == 1) {
                changed[id[i]] = 1;
                upd.pb(i);
            } else {
                calc.pb(i);
            }
        }
        for (int i = 1; i <= m; i++) if (!changed[i]) unchanged.pb(i);
        sort(all(unchanged), [&](const int &x, const int &y) {
            return w[x] > w[y];
        });
        sort(all(calc), [&](const int &x, const int &y) {
            return z[x] > z[y];
        });
        for (int i = l; i <= r; i++) {
            if (t[i] == 1) {
                w[id[i]] = z[i];
                changed[id[i]] = 0;
            } else {
                b[i - l].clear();
                for (int x: upd) if (w[id[x]] >= z[i]) b[i - l].pb(x);
            }
        }
        for (int j = 0, i = 0; i < calc.size(); i++) {
            while (j < unchanged.size() && w[unchanged[j]] >= z[calc[i]]) {
                join(u[unchanged[j]], v[unchanged[j]]);
                j++;
            }
            int sz = st.size();
            for (int x: b[calc[i] - l]) {
                join(u[id[x]], v[id[x]]);
            }
            ans[calc[i]] = -lab[root(id[calc[i]])];
            roll_back(sz);
        }
        roll_back(0);
    }
    for (int i = 1; i <= q; i++) if (ans[i] != -1) cout << ans[i] << '\n';
}

int32_t main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen(task".inp", "r", stdin);
    // freopen(task".out", "w", stdout);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}
/*

*/

Compilation message

bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:63:22: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   63 |     while (st.size() > sz) {
      |            ~~~~~~~~~~^~~~
bridges.cpp: In function 'void solve(int)':
bridges.cpp:112:34: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  112 |         for (int j = 0, i = 0; i < calc.size(); i++) {
      |                                  ^
bridges.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  113 |             while (j < unchanged.size() && w[unchanged[j]] >= z[calc[i]]) {
      |                      ^

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 13 ms 31572 KB Output is correct
3 Correct 51 ms 34024 KB Output is correct
4 Correct 17 ms 31700 KB Output is correct
5 Correct 54 ms 34136 KB Output is correct
6 Correct 40 ms 33748 KB Output is correct
7 Correct 47 ms 34656 KB Output is correct
8 Correct 49 ms 33820 KB Output is correct
9 Correct 59 ms 35528 KB Output is correct
10 Correct 49 ms 33996 KB Output is correct
11 Correct 52 ms 33828 KB Output is correct
12 Correct 59 ms 34028 KB Output is correct
13 Correct 56 ms 33920 KB Output is correct
14 Correct 59 ms 33884 KB Output is correct
15 Correct 58 ms 33928 KB Output is correct
16 Correct 54 ms 35184 KB Output is correct
17 Correct 55 ms 34640 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1181 ms 36968 KB Output is correct
2 Correct 1205 ms 37084 KB Output is correct
3 Correct 1201 ms 36988 KB Output is correct
4 Correct 1324 ms 36880 KB Output is correct
5 Correct 1247 ms 37148 KB Output is correct
6 Correct 1786 ms 38700 KB Output is correct
7 Correct 1762 ms 38684 KB Output is correct
8 Correct 1769 ms 38788 KB Output is correct
9 Correct 47 ms 32964 KB Output is correct
10 Correct 992 ms 38600 KB Output is correct
11 Correct 942 ms 38592 KB Output is correct
12 Correct 1061 ms 35248 KB Output is correct
13 Correct 1068 ms 38604 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 977 ms 36388 KB Output is correct
2 Correct 753 ms 37612 KB Output is correct
3 Correct 1136 ms 38136 KB Output is correct
4 Correct 932 ms 36664 KB Output is correct
5 Correct 59 ms 32988 KB Output is correct
6 Correct 1092 ms 36492 KB Output is correct
7 Correct 870 ms 36360 KB Output is correct
8 Correct 740 ms 36160 KB Output is correct
9 Correct 638 ms 34600 KB Output is correct
10 Correct 576 ms 34632 KB Output is correct
11 Correct 662 ms 37940 KB Output is correct
12 Correct 612 ms 37976 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1479 ms 35560 KB Output is correct
2 Correct 48 ms 34292 KB Output is correct
3 Correct 169 ms 36036 KB Output is correct
4 Correct 89 ms 35860 KB Output is correct
5 Correct 790 ms 38016 KB Output is correct
6 Correct 1474 ms 39628 KB Output is correct
7 Correct 783 ms 37820 KB Output is correct
8 Correct 738 ms 37108 KB Output is correct
9 Correct 727 ms 37220 KB Output is correct
10 Correct 766 ms 37084 KB Output is correct
11 Correct 1167 ms 38220 KB Output is correct
12 Correct 1055 ms 38252 KB Output is correct
13 Correct 1077 ms 38168 KB Output is correct
14 Correct 642 ms 37800 KB Output is correct
15 Correct 689 ms 37712 KB Output is correct
16 Correct 1448 ms 39180 KB Output is correct
17 Correct 1459 ms 39256 KB Output is correct
18 Correct 1434 ms 39380 KB Output is correct
19 Correct 1411 ms 39312 KB Output is correct
20 Correct 1191 ms 38640 KB Output is correct
21 Correct 1180 ms 38556 KB Output is correct
22 Correct 1344 ms 39052 KB Output is correct
23 Correct 785 ms 37584 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1181 ms 36968 KB Output is correct
2 Correct 1205 ms 37084 KB Output is correct
3 Correct 1201 ms 36988 KB Output is correct
4 Correct 1324 ms 36880 KB Output is correct
5 Correct 1247 ms 37148 KB Output is correct
6 Correct 1786 ms 38700 KB Output is correct
7 Correct 1762 ms 38684 KB Output is correct
8 Correct 1769 ms 38788 KB Output is correct
9 Correct 47 ms 32964 KB Output is correct
10 Correct 992 ms 38600 KB Output is correct
11 Correct 942 ms 38592 KB Output is correct
12 Correct 1061 ms 35248 KB Output is correct
13 Correct 1068 ms 38604 KB Output is correct
14 Correct 977 ms 36388 KB Output is correct
15 Correct 753 ms 37612 KB Output is correct
16 Correct 1136 ms 38136 KB Output is correct
17 Correct 932 ms 36664 KB Output is correct
18 Correct 59 ms 32988 KB Output is correct
19 Correct 1092 ms 36492 KB Output is correct
20 Correct 870 ms 36360 KB Output is correct
21 Correct 740 ms 36160 KB Output is correct
22 Correct 638 ms 34600 KB Output is correct
23 Correct 576 ms 34632 KB Output is correct
24 Correct 662 ms 37940 KB Output is correct
25 Correct 612 ms 37976 KB Output is correct
26 Correct 1170 ms 37076 KB Output is correct
27 Correct 1465 ms 38604 KB Output is correct
28 Correct 1245 ms 36988 KB Output is correct
29 Correct 895 ms 36672 KB Output is correct
30 Correct 1378 ms 38632 KB Output is correct
31 Correct 1415 ms 38540 KB Output is correct
32 Correct 1414 ms 38772 KB Output is correct
33 Correct 1215 ms 36976 KB Output is correct
34 Correct 1218 ms 36808 KB Output is correct
35 Correct 1234 ms 36868 KB Output is correct
36 Correct 921 ms 36744 KB Output is correct
37 Correct 918 ms 36700 KB Output is correct
38 Correct 898 ms 36516 KB Output is correct
39 Correct 755 ms 35068 KB Output is correct
40 Correct 747 ms 35200 KB Output is correct
41 Correct 749 ms 35076 KB Output is correct
42 Correct 732 ms 37844 KB Output is correct
43 Correct 748 ms 37912 KB Output is correct
44 Correct 746 ms 37956 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 13 ms 31572 KB Output is correct
3 Correct 51 ms 34024 KB Output is correct
4 Correct 17 ms 31700 KB Output is correct
5 Correct 54 ms 34136 KB Output is correct
6 Correct 40 ms 33748 KB Output is correct
7 Correct 47 ms 34656 KB Output is correct
8 Correct 49 ms 33820 KB Output is correct
9 Correct 59 ms 35528 KB Output is correct
10 Correct 49 ms 33996 KB Output is correct
11 Correct 52 ms 33828 KB Output is correct
12 Correct 59 ms 34028 KB Output is correct
13 Correct 56 ms 33920 KB Output is correct
14 Correct 59 ms 33884 KB Output is correct
15 Correct 58 ms 33928 KB Output is correct
16 Correct 54 ms 35184 KB Output is correct
17 Correct 55 ms 34640 KB Output is correct
18 Correct 1181 ms 36968 KB Output is correct
19 Correct 1205 ms 37084 KB Output is correct
20 Correct 1201 ms 36988 KB Output is correct
21 Correct 1324 ms 36880 KB Output is correct
22 Correct 1247 ms 37148 KB Output is correct
23 Correct 1786 ms 38700 KB Output is correct
24 Correct 1762 ms 38684 KB Output is correct
25 Correct 1769 ms 38788 KB Output is correct
26 Correct 47 ms 32964 KB Output is correct
27 Correct 992 ms 38600 KB Output is correct
28 Correct 942 ms 38592 KB Output is correct
29 Correct 1061 ms 35248 KB Output is correct
30 Correct 1068 ms 38604 KB Output is correct
31 Correct 977 ms 36388 KB Output is correct
32 Correct 753 ms 37612 KB Output is correct
33 Correct 1136 ms 38136 KB Output is correct
34 Correct 932 ms 36664 KB Output is correct
35 Correct 59 ms 32988 KB Output is correct
36 Correct 1092 ms 36492 KB Output is correct
37 Correct 870 ms 36360 KB Output is correct
38 Correct 740 ms 36160 KB Output is correct
39 Correct 638 ms 34600 KB Output is correct
40 Correct 576 ms 34632 KB Output is correct
41 Correct 662 ms 37940 KB Output is correct
42 Correct 612 ms 37976 KB Output is correct
43 Correct 1479 ms 35560 KB Output is correct
44 Correct 48 ms 34292 KB Output is correct
45 Correct 169 ms 36036 KB Output is correct
46 Correct 89 ms 35860 KB Output is correct
47 Correct 790 ms 38016 KB Output is correct
48 Correct 1474 ms 39628 KB Output is correct
49 Correct 783 ms 37820 KB Output is correct
50 Correct 738 ms 37108 KB Output is correct
51 Correct 727 ms 37220 KB Output is correct
52 Correct 766 ms 37084 KB Output is correct
53 Correct 1167 ms 38220 KB Output is correct
54 Correct 1055 ms 38252 KB Output is correct
55 Correct 1077 ms 38168 KB Output is correct
56 Correct 642 ms 37800 KB Output is correct
57 Correct 689 ms 37712 KB Output is correct
58 Correct 1448 ms 39180 KB Output is correct
59 Correct 1459 ms 39256 KB Output is correct
60 Correct 1434 ms 39380 KB Output is correct
61 Correct 1411 ms 39312 KB Output is correct
62 Correct 1191 ms 38640 KB Output is correct
63 Correct 1180 ms 38556 KB Output is correct
64 Correct 1344 ms 39052 KB Output is correct
65 Correct 785 ms 37584 KB Output is correct
66 Correct 1170 ms 37076 KB Output is correct
67 Correct 1465 ms 38604 KB Output is correct
68 Correct 1245 ms 36988 KB Output is correct
69 Correct 895 ms 36672 KB Output is correct
70 Correct 1378 ms 38632 KB Output is correct
71 Correct 1415 ms 38540 KB Output is correct
72 Correct 1414 ms 38772 KB Output is correct
73 Correct 1215 ms 36976 KB Output is correct
74 Correct 1218 ms 36808 KB Output is correct
75 Correct 1234 ms 36868 KB Output is correct
76 Correct 921 ms 36744 KB Output is correct
77 Correct 918 ms 36700 KB Output is correct
78 Correct 898 ms 36516 KB Output is correct
79 Correct 755 ms 35068 KB Output is correct
80 Correct 747 ms 35200 KB Output is correct
81 Correct 749 ms 35076 KB Output is correct
82 Correct 732 ms 37844 KB Output is correct
83 Correct 748 ms 37912 KB Output is correct
84 Correct 746 ms 37956 KB Output is correct
85 Correct 1851 ms 41828 KB Output is correct
86 Correct 192 ms 37884 KB Output is correct
87 Correct 127 ms 39232 KB Output is correct
88 Correct 1098 ms 42228 KB Output is correct
89 Correct 1798 ms 42232 KB Output is correct
90 Correct 1104 ms 41756 KB Output is correct
91 Correct 1247 ms 39660 KB Output is correct
92 Correct 1225 ms 39612 KB Output is correct
93 Correct 1742 ms 40984 KB Output is correct
94 Correct 1503 ms 40792 KB Output is correct
95 Correct 1509 ms 40952 KB Output is correct
96 Correct 1816 ms 42360 KB Output is correct
97 Correct 827 ms 38756 KB Output is correct
98 Correct 934 ms 41720 KB Output is correct
99 Correct 1916 ms 42068 KB Output is correct
100 Correct 1872 ms 41664 KB Output is correct
101 Correct 1843 ms 41940 KB Output is correct
102 Correct 1837 ms 42028 KB Output is correct
103 Correct 2007 ms 42752 KB Output is correct
104 Correct 2004 ms 42680 KB Output is correct
105 Correct 1462 ms 42492 KB Output is correct
106 Correct 1207 ms 42436 KB Output is correct
107 Correct 1393 ms 39280 KB Output is correct
108 Correct 1875 ms 41780 KB Output is correct
109 Correct 1377 ms 41328 KB Output is correct