oj.uz

답안 #869024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869024 2023-11-03T02:01:04 Z TS_2392 다리 (APIO19_bridges) C++14
100 / 100
 1593 ms 215524 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
// using namespace __gnu_pbds;

#define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED         ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL            cout << '\n'
#define dbg(x)        cout << #x << " = " << (x) << ' '
#define dbgp(x)       cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}

#define epl           emplace
#define pb            push_back
#define eb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair

#define sqr(x)        ((x) * (x))
#define all(x)        (x).begin(), (x).end()
#define rall(x)       (x).rbegin(), (x).rend()
#define lwb           lower_bound
#define upb           upper_bound

#define clz           __builtin_clzll // or __builtin_clz
#define ctz           __builtin_ctzll // or __builtin_ctz
#define pct           __builtin_popcountll // or __builtin_popcount

typedef long long            ll;
typedef long double          ldb;
typedef unsigned int         uint;
typedef unsigned long long   ull;
typedef pair<ll, ll>         pll;
typedef pair<ll, int>        pli;
typedef pair<int, ll>        pil;
typedef pair<int, int>       pii;
typedef pair<ldb, ldb>       pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
template<class T> void remDup(vector<T> &v){sort(all(v)); v.erase(unique(all(v)),v.end());}

// int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int N = 1e5 + 3, bz = 1000;
int n, m, q, pr[N], res[N];
int node_a[N], node_b[N], w[N];
int type[N], x[N], y[N];
bool changed[N];
vector<int> to_unite[N];
stack<pii> stk;
int find_set(int u){
    return pr[u] < 0 ? u : find_set(pr[u]);
}
void unite(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if(u == v) return;
    if(pr[u] > pr[v]) swap(u, v);
    stk.push({u, pr[u]});
    stk.push({v, pr[v]});
    pr[u] += pr[v]; pr[v] = u;
}
void rollback(int sz){
    while(stk.size() > sz){
        pii x = stk.top();
        pr[x.fi] = x.se; stk.pop();
    }
}
void TS_2392(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> node_a[i] >> node_b[i] >> w[i];
    }
    cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> type[i] >> x[i] >> y[i];
    }
    for(int l = 1; l <= q; l += bz){
        int r = min(l + bz - 1, q);
        memset(pr, 255, sizeof(pr));
        memset(changed, 0, sizeof(changed));
        vector<int> upd, ask, remain;
        for(int i = l; i <= r; ++i){
            if(type[i] == 1){
                changed[x[i]] = true;
                upd.eb(i);
            }
            else ask.eb(i);
        }
        for(int i = 1; i <= m; ++i) if(!changed[i]){
            remain.eb(i);
        }
        sort(all(remain), [&](const int &i1, const int &i2){
            return w[i1] > w[i2];
        });
        for(int i = l; i <= r; ++i){
            if(type[i] == 1){
                w[x[i]] = y[i];
            }
            else{
                for(int &j : upd) if(w[x[j]] >= y[i]){
                    to_unite[i].eb(x[j]);
                }
            }
        }
        sort(all(ask), [&](const int &i1, const int &i2){
            return y[i1] > y[i2];
        });
        int ptr = 0;
        for(int &i : ask){
            while(ptr < remain.size() && y[i] <= w[remain[ptr]]){
                unite(node_a[remain[ptr]], node_b[remain[ptr]]);
                ++ptr;
            }
            int sz = stk.size();
            for(int &j : to_unite[i]){
                unite(node_a[j], node_b[j]);
            }
            res[i] = -pr[find_set(x[i])];
            rollback(sz);
        }
    }
    for(int i = 1; i <= q; ++i) if(res[i] > 0){
        cout << res[i] << '\n';
    }
}
int main(){
    SPEED; fileIO("text");
    int numtest = 1; //cin >> numtest;
    for(int itest = 1; itest <= numtest; ++itest){
        // cout << "Case #" << itest << ": ";
        TS_2392(); //cout << '\n';
    }
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * small cases, special cases (n = 1 ???)
 * do something instead of nothing: code bruteforce
 * WRITE STUFF DOWN and STAY ORGANIZED
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:72:22: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     while(stk.size() > sz){
      |           ~~~~~~~~~~~^~~~
bridges.cpp: In function 'void TS_2392()':
bridges.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             while(ptr < remain.size() && y[i] <= w[remain[ptr]]){
      |                   ~~~~^~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:136:12: note: in expansion of macro 'fileIO'
  136 |     SPEED; fileIO("text");
      |            ^~~~~~
bridges.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:136:12: note: in expansion of macro 'fileIO'
  136 |     SPEED; fileIO("text");
      |            ^~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 27 ms 11900 KB Output is correct
4 Correct 4 ms 5212 KB Output is correct
5 Correct 31 ms 12724 KB Output is correct
6 Correct 22 ms 13144 KB Output is correct
7 Correct 27 ms 12712 KB Output is correct
8 Correct 33 ms 11140 KB Output is correct
9 Correct 42 ms 17176 KB Output is correct
10 Correct 33 ms 12120 KB Output is correct
11 Correct 36 ms 12176 KB Output is correct
12 Correct 40 ms 14420 KB Output is correct
13 Correct 38 ms 12372 KB Output is correct
14 Correct 36 ms 11540 KB Output is correct
15 Correct 39 ms 12680 KB Output is correct
16 Correct 31 ms 15188 KB Output is correct
17 Correct 32 ms 14420 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1048 ms 156832 KB Output is correct
2 Correct 1064 ms 156696 KB Output is correct
3 Correct 1067 ms 156996 KB Output is correct
4 Correct 1081 ms 157572 KB Output is correct
5 Correct 1094 ms 157020 KB Output is correct
6 Correct 1296 ms 215524 KB Output is correct
7 Correct 1311 ms 211436 KB Output is correct
8 Correct 1329 ms 211040 KB Output is correct
9 Correct 27 ms 7000 KB Output is correct
10 Correct 810 ms 181316 KB Output is correct
11 Correct 772 ms 180504 KB Output is correct
12 Correct 870 ms 137192 KB Output is correct
13 Correct 880 ms 129348 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 832 ms 128432 KB Output is correct
2 Correct 638 ms 113000 KB Output is correct
3 Correct 944 ms 156248 KB Output is correct
4 Correct 827 ms 128024 KB Output is correct
5 Correct 27 ms 6996 KB Output is correct
6 Correct 986 ms 147520 KB Output is correct
7 Correct 771 ms 119744 KB Output is correct
8 Correct 680 ms 103756 KB Output is correct
9 Correct 573 ms 96372 KB Output is correct
10 Correct 521 ms 84964 KB Output is correct
11 Correct 580 ms 92552 KB Output is correct
12 Correct 521 ms 81660 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1251 ms 91224 KB Output is correct
2 Correct 36 ms 6924 KB Output is correct
3 Correct 125 ms 8488 KB Output is correct
4 Correct 60 ms 8520 KB Output is correct
5 Correct 659 ms 89892 KB Output is correct
6 Correct 1199 ms 91012 KB Output is correct
7 Correct 647 ms 89456 KB Output is correct
8 Correct 616 ms 91008 KB Output is correct
9 Correct 630 ms 90720 KB Output is correct
10 Correct 608 ms 90816 KB Output is correct
11 Correct 925 ms 91788 KB Output is correct
12 Correct 942 ms 92604 KB Output is correct
13 Correct 935 ms 91792 KB Output is correct
14 Correct 586 ms 89644 KB Output is correct
15 Correct 615 ms 89588 KB Output is correct
16 Correct 1236 ms 92592 KB Output is correct
17 Correct 1251 ms 91920 KB Output is correct
18 Correct 1242 ms 93336 KB Output is correct
19 Correct 1226 ms 92436 KB Output is correct
20 Correct 1041 ms 91952 KB Output is correct
21 Correct 1042 ms 91924 KB Output is correct
22 Correct 1191 ms 91084 KB Output is correct
23 Correct 750 ms 83184 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1048 ms 156832 KB Output is correct
2 Correct 1064 ms 156696 KB Output is correct
3 Correct 1067 ms 156996 KB Output is correct
4 Correct 1081 ms 157572 KB Output is correct
5 Correct 1094 ms 157020 KB Output is correct
6 Correct 1296 ms 215524 KB Output is correct
7 Correct 1311 ms 211436 KB Output is correct
8 Correct 1329 ms 211040 KB Output is correct
9 Correct 27 ms 7000 KB Output is correct
10 Correct 810 ms 181316 KB Output is correct
11 Correct 772 ms 180504 KB Output is correct
12 Correct 870 ms 137192 KB Output is correct
13 Correct 880 ms 129348 KB Output is correct
14 Correct 832 ms 128432 KB Output is correct
15 Correct 638 ms 113000 KB Output is correct
16 Correct 944 ms 156248 KB Output is correct
17 Correct 827 ms 128024 KB Output is correct
18 Correct 27 ms 6996 KB Output is correct
19 Correct 986 ms 147520 KB Output is correct
20 Correct 771 ms 119744 KB Output is correct
21 Correct 680 ms 103756 KB Output is correct
22 Correct 573 ms 96372 KB Output is correct
23 Correct 521 ms 84964 KB Output is correct
24 Correct 580 ms 92552 KB Output is correct
25 Correct 521 ms 81660 KB Output is correct
26 Correct 1057 ms 156728 KB Output is correct
27 Correct 1236 ms 185920 KB Output is correct
28 Correct 1104 ms 155656 KB Output is correct
29 Correct 801 ms 111724 KB Output is correct
30 Correct 1177 ms 173420 KB Output is correct
31 Correct 1193 ms 175708 KB Output is correct
32 Correct 1201 ms 176340 KB Output is correct
33 Correct 1073 ms 156184 KB Output is correct
34 Correct 1078 ms 156592 KB Output is correct
35 Correct 1087 ms 155640 KB Output is correct
36 Correct 848 ms 119452 KB Output is correct
37 Correct 840 ms 118304 KB Output is correct
38 Correct 831 ms 116504 KB Output is correct
39 Correct 711 ms 103428 KB Output is correct
40 Correct 699 ms 101900 KB Output is correct
41 Correct 700 ms 101284 KB Output is correct
42 Correct 687 ms 98488 KB Output is correct
43 Correct 674 ms 97980 KB Output is correct
44 Correct 678 ms 97008 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 27 ms 11900 KB Output is correct
4 Correct 4 ms 5212 KB Output is correct
5 Correct 31 ms 12724 KB Output is correct
6 Correct 22 ms 13144 KB Output is correct
7 Correct 27 ms 12712 KB Output is correct
8 Correct 33 ms 11140 KB Output is correct
9 Correct 42 ms 17176 KB Output is correct
10 Correct 33 ms 12120 KB Output is correct
11 Correct 36 ms 12176 KB Output is correct
12 Correct 40 ms 14420 KB Output is correct
13 Correct 38 ms 12372 KB Output is correct
14 Correct 36 ms 11540 KB Output is correct
15 Correct 39 ms 12680 KB Output is correct
16 Correct 31 ms 15188 KB Output is correct
17 Correct 32 ms 14420 KB Output is correct
18 Correct 1048 ms 156832 KB Output is correct
19 Correct 1064 ms 156696 KB Output is correct
20 Correct 1067 ms 156996 KB Output is correct
21 Correct 1081 ms 157572 KB Output is correct
22 Correct 1094 ms 157020 KB Output is correct
23 Correct 1296 ms 215524 KB Output is correct
24 Correct 1311 ms 211436 KB Output is correct
25 Correct 1329 ms 211040 KB Output is correct
26 Correct 27 ms 7000 KB Output is correct
27 Correct 810 ms 181316 KB Output is correct
28 Correct 772 ms 180504 KB Output is correct
29 Correct 870 ms 137192 KB Output is correct
30 Correct 880 ms 129348 KB Output is correct
31 Correct 832 ms 128432 KB Output is correct
32 Correct 638 ms 113000 KB Output is correct
33 Correct 944 ms 156248 KB Output is correct
34 Correct 827 ms 128024 KB Output is correct
35 Correct 27 ms 6996 KB Output is correct
36 Correct 986 ms 147520 KB Output is correct
37 Correct 771 ms 119744 KB Output is correct
38 Correct 680 ms 103756 KB Output is correct
39 Correct 573 ms 96372 KB Output is correct
40 Correct 521 ms 84964 KB Output is correct
41 Correct 580 ms 92552 KB Output is correct
42 Correct 521 ms 81660 KB Output is correct
43 Correct 1251 ms 91224 KB Output is correct
44 Correct 36 ms 6924 KB Output is correct
45 Correct 125 ms 8488 KB Output is correct
46 Correct 60 ms 8520 KB Output is correct
47 Correct 659 ms 89892 KB Output is correct
48 Correct 1199 ms 91012 KB Output is correct
49 Correct 647 ms 89456 KB Output is correct
50 Correct 616 ms 91008 KB Output is correct
51 Correct 630 ms 90720 KB Output is correct
52 Correct 608 ms 90816 KB Output is correct
53 Correct 925 ms 91788 KB Output is correct
54 Correct 942 ms 92604 KB Output is correct
55 Correct 935 ms 91792 KB Output is correct
56 Correct 586 ms 89644 KB Output is correct
57 Correct 615 ms 89588 KB Output is correct
58 Correct 1236 ms 92592 KB Output is correct
59 Correct 1251 ms 91920 KB Output is correct
60 Correct 1242 ms 93336 KB Output is correct
61 Correct 1226 ms 92436 KB Output is correct
62 Correct 1041 ms 91952 KB Output is correct
63 Correct 1042 ms 91924 KB Output is correct
64 Correct 1191 ms 91084 KB Output is correct
65 Correct 750 ms 83184 KB Output is correct
66 Correct 1057 ms 156728 KB Output is correct
67 Correct 1236 ms 185920 KB Output is correct
68 Correct 1104 ms 155656 KB Output is correct
69 Correct 801 ms 111724 KB Output is correct
70 Correct 1177 ms 173420 KB Output is correct
71 Correct 1193 ms 175708 KB Output is correct
72 Correct 1201 ms 176340 KB Output is correct
73 Correct 1073 ms 156184 KB Output is correct
74 Correct 1078 ms 156592 KB Output is correct
75 Correct 1087 ms 155640 KB Output is correct
76 Correct 848 ms 119452 KB Output is correct
77 Correct 840 ms 118304 KB Output is correct
78 Correct 831 ms 116504 KB Output is correct
79 Correct 711 ms 103428 KB Output is correct
80 Correct 699 ms 101900 KB Output is correct
81 Correct 700 ms 101284 KB Output is correct
82 Correct 687 ms 98488 KB Output is correct
83 Correct 674 ms 97980 KB Output is correct
84 Correct 678 ms 97008 KB Output is correct
85 Correct 1582 ms 158104 KB Output is correct
86 Correct 154 ms 14720 KB Output is correct
87 Correct 91 ms 18972 KB Output is correct
88 Correct 919 ms 170208 KB Output is correct
89 Correct 1555 ms 156640 KB Output is correct
90 Correct 931 ms 178388 KB Output is correct
91 Correct 1109 ms 156816 KB Output is correct
92 Correct 1102 ms 156440 KB Output is correct
93 Correct 1399 ms 194508 KB Output is correct
94 Correct 1292 ms 158492 KB Output is correct
95 Correct 1304 ms 158612 KB Output is correct
96 Correct 1321 ms 200064 KB Output is correct
97 Correct 769 ms 122644 KB Output is correct
98 Correct 761 ms 120196 KB Output is correct
99 Correct 1593 ms 160156 KB Output is correct
100 Correct 1566 ms 158620 KB Output is correct
101 Correct 1593 ms 160112 KB Output is correct
102 Correct 1573 ms 159032 KB Output is correct
103 Correct 1419 ms 205164 KB Output is correct
104 Correct 1417 ms 204112 KB Output is correct
105 Correct 1187 ms 131664 KB Output is correct
106 Correct 1022 ms 111552 KB Output is correct
107 Correct 1183 ms 138348 KB Output is correct
108 Correct 1497 ms 192340 KB Output is correct
109 Correct 1012 ms 189648 KB Output is correct