oj.uz

Submission #886499

# Submission time Handle Problem Language Result Execution time Memory
886499 2023-12-12T08:59:02 Z Kutan Bridges (APIO19_bridges) C++14
100 / 100
 2602 ms 11660 KB 
// Cao Quang Hung
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
 
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long , long long>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define dem(x) __builtin_popcount(x)
#define Mask(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ln '\n'
#define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
///mt19937 rnd(time(0));
 
const int INF = 1e9 , mod = 1e9 + 7;
 
template <class T1, class T2>
inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }
 
template <class T1 , class T2>
inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}
 
template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }
 
template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }
 
template <class T>
inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }
 
template <class T>
inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }
 
#define PROB "a"
void file(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
}
void sinh_(){
//    srand(time(0));
//    freopen(PROB".inp" , "w" , stdout);
//    int n;
}
 
typedef long long ll;
typedef double db;
const int N = 1e5 + 5;
const int S = 350;
 
int n, m, q;
int par[N], sz[N];
int mark[N] = {}, num = 0, numRemain, curW[N];
int ans[N];
 
struct Data{
    int u, su, v, sv;
    Data(int _u = 0, int _su = 0, int _v = 0, int _sv = 0) {
        u = _u, su = _su, v = _v, sv = _sv;
    }
} st[N]; 
int roll_back_size;
 
struct edge{
    int u, v, w;
    edge(int _u = 0, int _v = 0, int _w = 0) {
        u = _u, v = _v, w = _w;
    }
    bool operator < (const edge &other) const {
        return w > other.w;
    }
} Edge[N], remained_edge[N];
 
struct query{
    int type, u, w;
    query(int _type = 0, int _u = 0, int _w = 0) {
        type = _type, u = _u, w = _w;
    }
} Query[N];
 
 
void readip(){
    cin >> n >> m;
    REP(i, 1, m) cin >> Edge[i].u >> Edge[i].v >> Edge[i].w;
    cin >> q;
    REP(i, 1, q) cin >> Query[i].type >> Query[i].u >> Query[i].w;
}
 
void init() {
    REP(i, 1, n) par[i] = i, sz[i] = 1;
    roll_back_size = 0;
}
 
int root(int x) { if (x == par[x]) return x; return root(par[x]); }
 
void unite(int u, int v, bool hold) {
    u = root(u) , v = root(v);
    if (u == v) return;
 
    if (!hold) st[++roll_back_size] = {u, sz[u], v, sz[v]};
 
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
}
 
void roll_back() {
    while(roll_back_size > 0) {
        const auto &[u, su, v, sv] = st[roll_back_size--];
        par[u] = u, sz[u] = su;
        par[v] = v, sz[v] = sv;
    }
}
 
void solve(){   
    vector<int> active_edges;   
    vector<int> order;      
    
    for (int l = 1; l <= q; ++l) {
        int r = min(q, l + S - 1);
        ++num;
 
        active_edges.clear();
        order.clear();
 
        REP(i, l, r) {
            if (Query[i].type == 1) {
                if (mark[Query[i].u] != num) {
                    mark[Query[i].u] = num;
                    active_edges.eb(Query[i].u);
                }
            }
            else order.eb(i);
        }   
            
 
        numRemain = 0;
        REP(i, 1, m) if (mark[i] != num) remained_edge[++numRemain] = Edge[i];
        sort(remained_edge + 1, remained_edge + numRemain + 1);
 
        sort(ALL(order), [&](const int &x, const int &y){
            return Query[x].w > Query[y].w;
        });
 
        init();
        int pt = 1;
        for (int i : order) {
            while(pt <= numRemain && remained_edge[pt].w >= Query[i].w) {
                unite(remained_edge[pt].u, remained_edge[pt].v, 1);
                ++pt;
            }
 
            for (int id : active_edges) curW[id] = Edge[id].w;
 
            REP(k, l, i) if (Query[k].type == 1)
                curW[Query[k].u] = Query[k].w;
            
            for (int id : active_edges) if (curW[id] >= Query[i].w) 
                unite(Edge[id].u, Edge[id].v, 0);
 
            ans[i] = sz[root(Query[i].u)];
            roll_back();
        }
 
        REP(k, l, r) if (Query[k].type == 1)
            Edge[Query[k].u].w = Query[k].w;
        l = r;
    }
 
    REP(i, 1, q) if (Query[i].type == 2) cout << ans[i] << ln;
}
 
int main(){
    sinh_();
    io_faster
    file();
    int t = 1;
//    cin >> t;
    while (t--){
        readip();
        solve();
    }
}

Compilation message

bridges.cpp: In function 'void readip()':
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:173:5: note: in expansion of macro 'REP'
  173 |     REP(i, 1, m) cin >> Edge[i].u >> Edge[i].v >> Edge[i].w;
      |     ^~~
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:175:5: note: in expansion of macro 'REP'
  175 |     REP(i, 1, q) cin >> Query[i].type >> Query[i].u >> Query[i].w;
      |     ^~~
bridges.cpp: In function 'void init()':
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:179:5: note: in expansion of macro 'REP'
  179 |     REP(i, 1, n) par[i] = i, sz[i] = 1;
      |     ^~~
bridges.cpp: In function 'void roll_back()':
bridges.cpp:198:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  198 |         const auto &[u, su, v, sv] = st[roll_back_size--];
      |                     ^
bridges.cpp: In function 'void solve()':
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:215:9: note: in expansion of macro 'REP'
  215 |         REP(i, l, r) {
      |         ^~~
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:227:9: note: in expansion of macro 'REP'
  227 |         REP(i, 1, m) if (mark[i] != num) remained_edge[++numRemain] = Edge[i];
      |         ^~~
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:244:13: note: in expansion of macro 'REP'
  244 |             REP(k, l, i) if (Query[k].type == 1)
      |             ^~~
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:254:9: note: in expansion of macro 'REP'
  254 |         REP(k, l, r) if (Query[k].type == 1)
      |         ^~~
bridges.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
bridges.cpp:259:5: note: in expansion of macro 'REP'
  259 |     REP(i, 1, q) if (Query[i].type == 2) cout << ans[i] << ln;
      |     ^~~
bridges.cpp: In function 'void file()':
bridges.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 11 ms 6980 KB Output is correct
4 Correct 5 ms 6748 KB Output is correct
5 Correct 8 ms 6800 KB Output is correct
6 Correct 7 ms 6748 KB Output is correct
7 Correct 7 ms 6808 KB Output is correct
8 Correct 9 ms 7004 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 8 ms 6748 KB Output is correct
11 Correct 8 ms 6804 KB Output is correct
12 Correct 9 ms 6748 KB Output is correct
13 Correct 10 ms 6944 KB Output is correct
14 Correct 9 ms 6904 KB Output is correct
15 Correct 9 ms 6744 KB Output is correct
16 Correct 7 ms 6748 KB Output is correct
17 Correct 8 ms 6748 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1162 ms 9872 KB Output is correct
2 Correct 1185 ms 10064 KB Output is correct
3 Correct 1229 ms 9832 KB Output is correct
4 Correct 1180 ms 9888 KB Output is correct
5 Correct 1173 ms 9816 KB Output is correct
6 Correct 1240 ms 9900 KB Output is correct
7 Correct 1230 ms 9904 KB Output is correct
8 Correct 1251 ms 9936 KB Output is correct
9 Correct 37 ms 8272 KB Output is correct
10 Correct 525 ms 8848 KB Output is correct
11 Correct 550 ms 8716 KB Output is correct
12 Correct 1146 ms 9812 KB Output is correct
13 Correct 1130 ms 9800 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 9348 KB Output is correct
2 Correct 264 ms 8532 KB Output is correct
3 Correct 776 ms 9084 KB Output is correct
4 Correct 759 ms 9552 KB Output is correct
5 Correct 49 ms 8276 KB Output is correct
6 Correct 798 ms 9232 KB Output is correct
7 Correct 761 ms 9256 KB Output is correct
8 Correct 751 ms 9276 KB Output is correct
9 Correct 725 ms 9584 KB Output is correct
10 Correct 722 ms 9552 KB Output is correct
11 Correct 706 ms 9240 KB Output is correct
12 Correct 691 ms 9296 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2506 ms 11176 KB Output is correct
2 Correct 38 ms 8276 KB Output is correct
3 Correct 257 ms 8536 KB Output is correct
4 Correct 108 ms 8784 KB Output is correct
5 Correct 1256 ms 9652 KB Output is correct
6 Correct 2407 ms 11176 KB Output is correct
7 Correct 1303 ms 9632 KB Output is correct
8 Correct 1105 ms 9840 KB Output is correct
9 Correct 1096 ms 10064 KB Output is correct
10 Correct 1125 ms 10080 KB Output is correct
11 Correct 1809 ms 10524 KB Output is correct
12 Correct 1761 ms 10836 KB Output is correct
13 Correct 1833 ms 10576 KB Output is correct
14 Correct 1161 ms 9888 KB Output is correct
15 Correct 1210 ms 10068 KB Output is correct
16 Correct 2492 ms 11104 KB Output is correct
17 Correct 2525 ms 11072 KB Output is correct
18 Correct 2478 ms 11660 KB Output is correct
19 Correct 2466 ms 11248 KB Output is correct
20 Correct 2080 ms 10776 KB Output is correct
21 Correct 2073 ms 10728 KB Output is correct
22 Correct 2396 ms 11168 KB Output is correct
23 Correct 1355 ms 9640 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1162 ms 9872 KB Output is correct
2 Correct 1185 ms 10064 KB Output is correct
3 Correct 1229 ms 9832 KB Output is correct
4 Correct 1180 ms 9888 KB Output is correct
5 Correct 1173 ms 9816 KB Output is correct
6 Correct 1240 ms 9900 KB Output is correct
7 Correct 1230 ms 9904 KB Output is correct
8 Correct 1251 ms 9936 KB Output is correct
9 Correct 37 ms 8272 KB Output is correct
10 Correct 525 ms 8848 KB Output is correct
11 Correct 550 ms 8716 KB Output is correct
12 Correct 1146 ms 9812 KB Output is correct
13 Correct 1130 ms 9800 KB Output is correct
14 Correct 779 ms 9348 KB Output is correct
15 Correct 264 ms 8532 KB Output is correct
16 Correct 776 ms 9084 KB Output is correct
17 Correct 759 ms 9552 KB Output is correct
18 Correct 49 ms 8276 KB Output is correct
19 Correct 798 ms 9232 KB Output is correct
20 Correct 761 ms 9256 KB Output is correct
21 Correct 751 ms 9276 KB Output is correct
22 Correct 725 ms 9584 KB Output is correct
23 Correct 722 ms 9552 KB Output is correct
24 Correct 706 ms 9240 KB Output is correct
25 Correct 691 ms 9296 KB Output is correct
26 Correct 1156 ms 9816 KB Output is correct
27 Correct 1237 ms 9852 KB Output is correct
28 Correct 1224 ms 9888 KB Output is correct
29 Correct 1175 ms 9812 KB Output is correct
30 Correct 1229 ms 9812 KB Output is correct
31 Correct 1239 ms 9808 KB Output is correct
32 Correct 1246 ms 9692 KB Output is correct
33 Correct 1204 ms 9896 KB Output is correct
34 Correct 1221 ms 10068 KB Output is correct
35 Correct 1209 ms 9896 KB Output is correct
36 Correct 1159 ms 10064 KB Output is correct
37 Correct 1166 ms 9824 KB Output is correct
38 Correct 1161 ms 10064 KB Output is correct
39 Correct 1144 ms 9848 KB Output is correct
40 Correct 1125 ms 10096 KB Output is correct
41 Correct 1149 ms 10068 KB Output is correct
42 Correct 1073 ms 10064 KB Output is correct
43 Correct 1090 ms 9812 KB Output is correct
44 Correct 1092 ms 9804 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 11 ms 6980 KB Output is correct
4 Correct 5 ms 6748 KB Output is correct
5 Correct 8 ms 6800 KB Output is correct
6 Correct 7 ms 6748 KB Output is correct
7 Correct 7 ms 6808 KB Output is correct
8 Correct 9 ms 7004 KB Output is correct
9 Correct 9 ms 6748 KB Output is correct
10 Correct 8 ms 6748 KB Output is correct
11 Correct 8 ms 6804 KB Output is correct
12 Correct 9 ms 6748 KB Output is correct
13 Correct 10 ms 6944 KB Output is correct
14 Correct 9 ms 6904 KB Output is correct
15 Correct 9 ms 6744 KB Output is correct
16 Correct 7 ms 6748 KB Output is correct
17 Correct 8 ms 6748 KB Output is correct
18 Correct 1162 ms 9872 KB Output is correct
19 Correct 1185 ms 10064 KB Output is correct
20 Correct 1229 ms 9832 KB Output is correct
21 Correct 1180 ms 9888 KB Output is correct
22 Correct 1173 ms 9816 KB Output is correct
23 Correct 1240 ms 9900 KB Output is correct
24 Correct 1230 ms 9904 KB Output is correct
25 Correct 1251 ms 9936 KB Output is correct
26 Correct 37 ms 8272 KB Output is correct
27 Correct 525 ms 8848 KB Output is correct
28 Correct 550 ms 8716 KB Output is correct
29 Correct 1146 ms 9812 KB Output is correct
30 Correct 1130 ms 9800 KB Output is correct
31 Correct 779 ms 9348 KB Output is correct
32 Correct 264 ms 8532 KB Output is correct
33 Correct 776 ms 9084 KB Output is correct
34 Correct 759 ms 9552 KB Output is correct
35 Correct 49 ms 8276 KB Output is correct
36 Correct 798 ms 9232 KB Output is correct
37 Correct 761 ms 9256 KB Output is correct
38 Correct 751 ms 9276 KB Output is correct
39 Correct 725 ms 9584 KB Output is correct
40 Correct 722 ms 9552 KB Output is correct
41 Correct 706 ms 9240 KB Output is correct
42 Correct 691 ms 9296 KB Output is correct
43 Correct 2506 ms 11176 KB Output is correct
44 Correct 38 ms 8276 KB Output is correct
45 Correct 257 ms 8536 KB Output is correct
46 Correct 108 ms 8784 KB Output is correct
47 Correct 1256 ms 9652 KB Output is correct
48 Correct 2407 ms 11176 KB Output is correct
49 Correct 1303 ms 9632 KB Output is correct
50 Correct 1105 ms 9840 KB Output is correct
51 Correct 1096 ms 10064 KB Output is correct
52 Correct 1125 ms 10080 KB Output is correct
53 Correct 1809 ms 10524 KB Output is correct
54 Correct 1761 ms 10836 KB Output is correct
55 Correct 1833 ms 10576 KB Output is correct
56 Correct 1161 ms 9888 KB Output is correct
57 Correct 1210 ms 10068 KB Output is correct
58 Correct 2492 ms 11104 KB Output is correct
59 Correct 2525 ms 11072 KB Output is correct
60 Correct 2478 ms 11660 KB Output is correct
61 Correct 2466 ms 11248 KB Output is correct
62 Correct 2080 ms 10776 KB Output is correct
63 Correct 2073 ms 10728 KB Output is correct
64 Correct 2396 ms 11168 KB Output is correct
65 Correct 1355 ms 9640 KB Output is correct
66 Correct 1156 ms 9816 KB Output is correct
67 Correct 1237 ms 9852 KB Output is correct
68 Correct 1224 ms 9888 KB Output is correct
69 Correct 1175 ms 9812 KB Output is correct
70 Correct 1229 ms 9812 KB Output is correct
71 Correct 1239 ms 9808 KB Output is correct
72 Correct 1246 ms 9692 KB Output is correct
73 Correct 1204 ms 9896 KB Output is correct
74 Correct 1221 ms 10068 KB Output is correct
75 Correct 1209 ms 9896 KB Output is correct
76 Correct 1159 ms 10064 KB Output is correct
77 Correct 1166 ms 9824 KB Output is correct
78 Correct 1161 ms 10064 KB Output is correct
79 Correct 1144 ms 9848 KB Output is correct
80 Correct 1125 ms 10096 KB Output is correct
81 Correct 1149 ms 10068 KB Output is correct
82 Correct 1073 ms 10064 KB Output is correct
83 Correct 1090 ms 9812 KB Output is correct
84 Correct 1092 ms 9804 KB Output is correct
85 Correct 2543 ms 10980 KB Output is correct
86 Correct 260 ms 8528 KB Output is correct
87 Correct 115 ms 8756 KB Output is correct
88 Correct 1339 ms 9556 KB Output is correct
89 Correct 2542 ms 10932 KB Output is correct
90 Correct 1353 ms 9640 KB Output is correct
91 Correct 1216 ms 9776 KB Output is correct
92 Correct 1214 ms 9896 KB Output is correct
93 Correct 1304 ms 9708 KB Output is correct
94 Correct 1979 ms 10272 KB Output is correct
95 Correct 1919 ms 10428 KB Output is correct
96 Correct 1924 ms 10244 KB Output is correct
97 Correct 1318 ms 9896 KB Output is correct
98 Correct 1296 ms 9444 KB Output is correct
99 Correct 2602 ms 11092 KB Output is correct
100 Correct 2597 ms 10832 KB Output is correct
101 Correct 2579 ms 10940 KB Output is correct
102 Correct 2583 ms 10940 KB Output is correct
103 Correct 2182 ms 10580 KB Output is correct
104 Correct 2182 ms 10480 KB Output is correct
105 Correct 2110 ms 10440 KB Output is correct
106 Correct 1824 ms 10340 KB Output is correct
107 Correct 2112 ms 10580 KB Output is correct
108 Correct 2484 ms 10952 KB Output is correct
109 Correct 1408 ms 9552 KB Output is correct