# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
888411 |
2023-12-17T10:26:48 Z |
nnhzzz |
Bridges (APIO19_bridges) |
C++17 |
|
1453 ms |
35168 KB |
#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 <locale>
#include <map>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
#include <chrono>
using namespace std;
#define __Nothing__ signed main()
#define BIT(i,j) (((i)>>(j))&1LL)
#define MASK(i) (1LL<<(i))
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define ll long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j)
#define REPD(i,be,en) for(int i = (be); i>=(en); i--)
#define REP(i,be,en) for(int i = (be); i<=(en); i++)
#define endl "\n"
#define MP make_pair
// #define int ll
//-----------------------------------------------------------------------------------------------//
int readInt(){
char c;
do{ c = getchar(); }while(c!='-' && !isdigit(c));
bool neg = (c=='-');
int res = neg?0:c-'0';
while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const ll LINF = 1e18;
const int INF = 1e9;
const int LOG = 20;
const int MAXN = 1e5+7;
const int N = 1e2+3;
const int MOD = 1e9+7;
const int BASE = 1e3;
const ld EPS = 1e-9;
const ld PI = acos(-1);
const int OFFSET = 1e3;
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//
struct DSU{
vi par,s;
stack<int> st;
int n;
void reset(){
iota(ALL(par),0);
REP(i,1,n) s[i] = 1;
}
int find(int u){
while(u!=par[u]) u = par[u];
return u;
}
bool same(int u, int v){
return find(u)==find(v);
}
void unite(int u, int v){
u = find(u); v = find(v);
if(u==v) return ;
if(s[u]<s[v]) swap(u,v);
s[u] += s[v];
par[v] = par[u];
st.push(v);
}
int getsize(int i){
i = find(i);
return s[i];
}
void rollback(int k){
while(SZ(st)>k){
int u = st.top(); st.pop();
s[par[u]] -= s[u];
par[u] = u;
}
}
int get(){
return SZ(st);
}
DSU(int _n):n(_n){
s.assign(n+3,1);
par.resize(n+3); iota(ALL(par),0);
}
};
int u[MAXN],v[MAXN],w[MAXN],op[MAXN],x[MAXN],y[MAXN],ok[MAXN],res[MAXN];
vi tmp[MAXN];
bool cmp1(int i, int j){
return y[i]>y[j];
}
bool cmp2(int i, int j){
return w[i]>w[j];
}
void solve(){
int n,m; cin >> n >> m;
int len = 2000;
REP(i,1,m) cin >> u[i] >> v[i] >> w[i];
int query; cin >> query;
REP(i,1,query) cin >> op[i] >> x[i] >> y[i];
DSU dsu(n);
REPDIS(l,1,query,len){
int r = min(query+1,l+len);
REP(i,1,m) ok[i] = 0;
dsu.reset();
vi ask,up,_up;
REP(i,l,r-1){
if(op[i]==1){
ok[x[i]] = 1;
up.push_back(i);
continue;
}
ask.push_back(i);
}
REP(i,1,m) if(ok[i]==0) _up.push_back(i);
REP(i,l,r-1){
if(op[i]==1){
w[x[i]] = y[i];
continue;
}
tmp[i-l].clear();
for(int &j:up){
if(w[x[j]]>=y[i]) tmp[i-l].push_back(x[j]);
}
}
sort(ALL(ask),cmp1);
sort(ALL(_up),cmp2);
int ptr = 0;
for(int &i:ask){
while(ptr<SZ(_up) && w[_up[ptr]]>=y[i]){
dsu.unite(u[_up[ptr]],v[_up[ptr]]);
++ptr;
}
int pre = dsu.get();
for(int &j:tmp[i-l]) dsu.unite(u[j],v[j]);
res[i] = dsu.getsize(x[i]);
dsu.rollback(pre);
}
}
REP(i,1,query){
if(op[i]==2){
cout << res[i] << endl;
}
}
}
__Nothing__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "test"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
#define task1 "sadge"
if(fopen(task1".inp","r")){
freopen(task1".inp","r",stdin);
freopen(task1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
/** /\_/\
* (= ._.)
* / >TL \>AC
**/
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:211:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
211 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:212:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
212 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:216:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | freopen(task1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:217:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | freopen(task1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
48 ms |
11860 KB |
Output is correct |
4 |
Correct |
4 ms |
4704 KB |
Output is correct |
5 |
Correct |
49 ms |
12136 KB |
Output is correct |
6 |
Correct |
33 ms |
12128 KB |
Output is correct |
7 |
Correct |
36 ms |
11948 KB |
Output is correct |
8 |
Correct |
51 ms |
11600 KB |
Output is correct |
9 |
Correct |
47 ms |
17456 KB |
Output is correct |
10 |
Correct |
53 ms |
11916 KB |
Output is correct |
11 |
Correct |
55 ms |
11604 KB |
Output is correct |
12 |
Correct |
66 ms |
12584 KB |
Output is correct |
13 |
Correct |
61 ms |
12116 KB |
Output is correct |
14 |
Correct |
59 ms |
11600 KB |
Output is correct |
15 |
Correct |
65 ms |
11908 KB |
Output is correct |
16 |
Correct |
44 ms |
16436 KB |
Output is correct |
17 |
Correct |
45 ms |
13656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
886 ms |
26272 KB |
Output is correct |
2 |
Correct |
919 ms |
25996 KB |
Output is correct |
3 |
Correct |
918 ms |
26108 KB |
Output is correct |
4 |
Correct |
944 ms |
26568 KB |
Output is correct |
5 |
Correct |
968 ms |
26352 KB |
Output is correct |
6 |
Correct |
1339 ms |
34004 KB |
Output is correct |
7 |
Correct |
1321 ms |
33896 KB |
Output is correct |
8 |
Correct |
1360 ms |
34132 KB |
Output is correct |
9 |
Correct |
28 ms |
5972 KB |
Output is correct |
10 |
Correct |
790 ms |
32040 KB |
Output is correct |
11 |
Correct |
710 ms |
32024 KB |
Output is correct |
12 |
Correct |
694 ms |
20140 KB |
Output is correct |
13 |
Correct |
731 ms |
33340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
743 ms |
22212 KB |
Output is correct |
2 |
Correct |
583 ms |
23376 KB |
Output is correct |
3 |
Correct |
801 ms |
28240 KB |
Output is correct |
4 |
Correct |
731 ms |
22276 KB |
Output is correct |
5 |
Correct |
27 ms |
5976 KB |
Output is correct |
6 |
Correct |
827 ms |
22112 KB |
Output is correct |
7 |
Correct |
669 ms |
22220 KB |
Output is correct |
8 |
Correct |
570 ms |
21732 KB |
Output is correct |
9 |
Correct |
399 ms |
15824 KB |
Output is correct |
10 |
Correct |
368 ms |
15764 KB |
Output is correct |
11 |
Correct |
484 ms |
28912 KB |
Output is correct |
12 |
Correct |
422 ms |
27668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
756 ms |
19744 KB |
Output is correct |
2 |
Correct |
27 ms |
5980 KB |
Output is correct |
3 |
Correct |
88 ms |
7856 KB |
Output is correct |
4 |
Correct |
53 ms |
8104 KB |
Output is correct |
5 |
Correct |
405 ms |
18960 KB |
Output is correct |
6 |
Correct |
743 ms |
19576 KB |
Output is correct |
7 |
Correct |
402 ms |
19016 KB |
Output is correct |
8 |
Correct |
358 ms |
18008 KB |
Output is correct |
9 |
Correct |
350 ms |
17944 KB |
Output is correct |
10 |
Correct |
355 ms |
17940 KB |
Output is correct |
11 |
Correct |
566 ms |
19120 KB |
Output is correct |
12 |
Correct |
550 ms |
19120 KB |
Output is correct |
13 |
Correct |
558 ms |
19272 KB |
Output is correct |
14 |
Correct |
384 ms |
19124 KB |
Output is correct |
15 |
Correct |
392 ms |
19020 KB |
Output is correct |
16 |
Correct |
756 ms |
20224 KB |
Output is correct |
17 |
Correct |
761 ms |
19856 KB |
Output is correct |
18 |
Correct |
774 ms |
19992 KB |
Output is correct |
19 |
Correct |
756 ms |
19848 KB |
Output is correct |
20 |
Correct |
637 ms |
19592 KB |
Output is correct |
21 |
Correct |
628 ms |
19340 KB |
Output is correct |
22 |
Correct |
728 ms |
19880 KB |
Output is correct |
23 |
Correct |
429 ms |
17912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
886 ms |
26272 KB |
Output is correct |
2 |
Correct |
919 ms |
25996 KB |
Output is correct |
3 |
Correct |
918 ms |
26108 KB |
Output is correct |
4 |
Correct |
944 ms |
26568 KB |
Output is correct |
5 |
Correct |
968 ms |
26352 KB |
Output is correct |
6 |
Correct |
1339 ms |
34004 KB |
Output is correct |
7 |
Correct |
1321 ms |
33896 KB |
Output is correct |
8 |
Correct |
1360 ms |
34132 KB |
Output is correct |
9 |
Correct |
28 ms |
5972 KB |
Output is correct |
10 |
Correct |
790 ms |
32040 KB |
Output is correct |
11 |
Correct |
710 ms |
32024 KB |
Output is correct |
12 |
Correct |
694 ms |
20140 KB |
Output is correct |
13 |
Correct |
731 ms |
33340 KB |
Output is correct |
14 |
Correct |
743 ms |
22212 KB |
Output is correct |
15 |
Correct |
583 ms |
23376 KB |
Output is correct |
16 |
Correct |
801 ms |
28240 KB |
Output is correct |
17 |
Correct |
731 ms |
22276 KB |
Output is correct |
18 |
Correct |
27 ms |
5976 KB |
Output is correct |
19 |
Correct |
827 ms |
22112 KB |
Output is correct |
20 |
Correct |
669 ms |
22220 KB |
Output is correct |
21 |
Correct |
570 ms |
21732 KB |
Output is correct |
22 |
Correct |
399 ms |
15824 KB |
Output is correct |
23 |
Correct |
368 ms |
15764 KB |
Output is correct |
24 |
Correct |
484 ms |
28912 KB |
Output is correct |
25 |
Correct |
422 ms |
27668 KB |
Output is correct |
26 |
Correct |
871 ms |
26388 KB |
Output is correct |
27 |
Correct |
1075 ms |
33364 KB |
Output is correct |
28 |
Correct |
913 ms |
26220 KB |
Output is correct |
29 |
Correct |
607 ms |
25748 KB |
Output is correct |
30 |
Correct |
1046 ms |
31720 KB |
Output is correct |
31 |
Correct |
1066 ms |
31948 KB |
Output is correct |
32 |
Correct |
1072 ms |
32388 KB |
Output is correct |
33 |
Correct |
918 ms |
26140 KB |
Output is correct |
34 |
Correct |
916 ms |
26524 KB |
Output is correct |
35 |
Correct |
927 ms |
26304 KB |
Output is correct |
36 |
Correct |
648 ms |
26132 KB |
Output is correct |
37 |
Correct |
639 ms |
25876 KB |
Output is correct |
38 |
Correct |
629 ms |
25940 KB |
Output is correct |
39 |
Correct |
446 ms |
20172 KB |
Output is correct |
40 |
Correct |
440 ms |
19960 KB |
Output is correct |
41 |
Correct |
443 ms |
20248 KB |
Output is correct |
42 |
Correct |
473 ms |
28184 KB |
Output is correct |
43 |
Correct |
469 ms |
28176 KB |
Output is correct |
44 |
Correct |
464 ms |
27660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
48 ms |
11860 KB |
Output is correct |
4 |
Correct |
4 ms |
4704 KB |
Output is correct |
5 |
Correct |
49 ms |
12136 KB |
Output is correct |
6 |
Correct |
33 ms |
12128 KB |
Output is correct |
7 |
Correct |
36 ms |
11948 KB |
Output is correct |
8 |
Correct |
51 ms |
11600 KB |
Output is correct |
9 |
Correct |
47 ms |
17456 KB |
Output is correct |
10 |
Correct |
53 ms |
11916 KB |
Output is correct |
11 |
Correct |
55 ms |
11604 KB |
Output is correct |
12 |
Correct |
66 ms |
12584 KB |
Output is correct |
13 |
Correct |
61 ms |
12116 KB |
Output is correct |
14 |
Correct |
59 ms |
11600 KB |
Output is correct |
15 |
Correct |
65 ms |
11908 KB |
Output is correct |
16 |
Correct |
44 ms |
16436 KB |
Output is correct |
17 |
Correct |
45 ms |
13656 KB |
Output is correct |
18 |
Correct |
886 ms |
26272 KB |
Output is correct |
19 |
Correct |
919 ms |
25996 KB |
Output is correct |
20 |
Correct |
918 ms |
26108 KB |
Output is correct |
21 |
Correct |
944 ms |
26568 KB |
Output is correct |
22 |
Correct |
968 ms |
26352 KB |
Output is correct |
23 |
Correct |
1339 ms |
34004 KB |
Output is correct |
24 |
Correct |
1321 ms |
33896 KB |
Output is correct |
25 |
Correct |
1360 ms |
34132 KB |
Output is correct |
26 |
Correct |
28 ms |
5972 KB |
Output is correct |
27 |
Correct |
790 ms |
32040 KB |
Output is correct |
28 |
Correct |
710 ms |
32024 KB |
Output is correct |
29 |
Correct |
694 ms |
20140 KB |
Output is correct |
30 |
Correct |
731 ms |
33340 KB |
Output is correct |
31 |
Correct |
743 ms |
22212 KB |
Output is correct |
32 |
Correct |
583 ms |
23376 KB |
Output is correct |
33 |
Correct |
801 ms |
28240 KB |
Output is correct |
34 |
Correct |
731 ms |
22276 KB |
Output is correct |
35 |
Correct |
27 ms |
5976 KB |
Output is correct |
36 |
Correct |
827 ms |
22112 KB |
Output is correct |
37 |
Correct |
669 ms |
22220 KB |
Output is correct |
38 |
Correct |
570 ms |
21732 KB |
Output is correct |
39 |
Correct |
399 ms |
15824 KB |
Output is correct |
40 |
Correct |
368 ms |
15764 KB |
Output is correct |
41 |
Correct |
484 ms |
28912 KB |
Output is correct |
42 |
Correct |
422 ms |
27668 KB |
Output is correct |
43 |
Correct |
756 ms |
19744 KB |
Output is correct |
44 |
Correct |
27 ms |
5980 KB |
Output is correct |
45 |
Correct |
88 ms |
7856 KB |
Output is correct |
46 |
Correct |
53 ms |
8104 KB |
Output is correct |
47 |
Correct |
405 ms |
18960 KB |
Output is correct |
48 |
Correct |
743 ms |
19576 KB |
Output is correct |
49 |
Correct |
402 ms |
19016 KB |
Output is correct |
50 |
Correct |
358 ms |
18008 KB |
Output is correct |
51 |
Correct |
350 ms |
17944 KB |
Output is correct |
52 |
Correct |
355 ms |
17940 KB |
Output is correct |
53 |
Correct |
566 ms |
19120 KB |
Output is correct |
54 |
Correct |
550 ms |
19120 KB |
Output is correct |
55 |
Correct |
558 ms |
19272 KB |
Output is correct |
56 |
Correct |
384 ms |
19124 KB |
Output is correct |
57 |
Correct |
392 ms |
19020 KB |
Output is correct |
58 |
Correct |
756 ms |
20224 KB |
Output is correct |
59 |
Correct |
761 ms |
19856 KB |
Output is correct |
60 |
Correct |
774 ms |
19992 KB |
Output is correct |
61 |
Correct |
756 ms |
19848 KB |
Output is correct |
62 |
Correct |
637 ms |
19592 KB |
Output is correct |
63 |
Correct |
628 ms |
19340 KB |
Output is correct |
64 |
Correct |
728 ms |
19880 KB |
Output is correct |
65 |
Correct |
429 ms |
17912 KB |
Output is correct |
66 |
Correct |
871 ms |
26388 KB |
Output is correct |
67 |
Correct |
1075 ms |
33364 KB |
Output is correct |
68 |
Correct |
913 ms |
26220 KB |
Output is correct |
69 |
Correct |
607 ms |
25748 KB |
Output is correct |
70 |
Correct |
1046 ms |
31720 KB |
Output is correct |
71 |
Correct |
1066 ms |
31948 KB |
Output is correct |
72 |
Correct |
1072 ms |
32388 KB |
Output is correct |
73 |
Correct |
918 ms |
26140 KB |
Output is correct |
74 |
Correct |
916 ms |
26524 KB |
Output is correct |
75 |
Correct |
927 ms |
26304 KB |
Output is correct |
76 |
Correct |
648 ms |
26132 KB |
Output is correct |
77 |
Correct |
639 ms |
25876 KB |
Output is correct |
78 |
Correct |
629 ms |
25940 KB |
Output is correct |
79 |
Correct |
446 ms |
20172 KB |
Output is correct |
80 |
Correct |
440 ms |
19960 KB |
Output is correct |
81 |
Correct |
443 ms |
20248 KB |
Output is correct |
82 |
Correct |
473 ms |
28184 KB |
Output is correct |
83 |
Correct |
469 ms |
28176 KB |
Output is correct |
84 |
Correct |
464 ms |
27660 KB |
Output is correct |
85 |
Correct |
1280 ms |
28004 KB |
Output is correct |
86 |
Correct |
127 ms |
14404 KB |
Output is correct |
87 |
Correct |
90 ms |
15820 KB |
Output is correct |
88 |
Correct |
802 ms |
31748 KB |
Output is correct |
89 |
Correct |
1224 ms |
28128 KB |
Output is correct |
90 |
Correct |
775 ms |
33104 KB |
Output is correct |
91 |
Correct |
960 ms |
26300 KB |
Output is correct |
92 |
Correct |
957 ms |
26036 KB |
Output is correct |
93 |
Correct |
1345 ms |
28440 KB |
Output is correct |
94 |
Correct |
1128 ms |
27308 KB |
Output is correct |
95 |
Correct |
1130 ms |
27504 KB |
Output is correct |
96 |
Correct |
1335 ms |
31664 KB |
Output is correct |
97 |
Correct |
527 ms |
20892 KB |
Output is correct |
98 |
Correct |
577 ms |
33800 KB |
Output is correct |
99 |
Correct |
1278 ms |
28280 KB |
Output is correct |
100 |
Correct |
1264 ms |
28244 KB |
Output is correct |
101 |
Correct |
1294 ms |
28136 KB |
Output is correct |
102 |
Correct |
1278 ms |
28352 KB |
Output is correct |
103 |
Correct |
1453 ms |
34192 KB |
Output is correct |
104 |
Correct |
1422 ms |
34156 KB |
Output is correct |
105 |
Correct |
1006 ms |
35168 KB |
Output is correct |
106 |
Correct |
774 ms |
33464 KB |
Output is correct |
107 |
Correct |
879 ms |
21636 KB |
Output is correct |
108 |
Correct |
1244 ms |
28424 KB |
Output is correct |
109 |
Correct |
958 ms |
30872 KB |
Output is correct |