oj.uz

답안 #941663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941663 2024-03-09T09:18:43 Z Baizho 다리 (APIO19_bridges) C++14
100 / 100
 2207 ms 209232 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt,sse3,avx")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(1e5)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
//const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }

int n, m, q, u[N], v[N], d[N], t[N], x[N], y[N], par[N], siz[N], ans[N], changed[N];
vector<int> unchanged, ask, change, ex[N];

const int B = 600;

int findpar(int v) {
	if(v == par[v]) return v;
	return findpar(par[v]);
}

vector<pair<pair<int, int>, int> > dat;

void rollback(int s) {
	while(dat.size() > s) {
		int a = dat.back().ff.ff, b = dat.back().ff.ss, parb = dat.back().ss;
		par[b] = parb;
		siz[a] -= siz[b];
		dat.pop_back();
	}
}

void combine(int a, int b) {
	a = findpar(a), b = findpar(b);
	if(a != b) {
		if(siz[a] < siz[b]) swap(a, b);
		dat.pb({{a, b}, par[b]});
		par[b] = a;
		siz[a] += siz[b];
	}
}

void Baizho() {
	cin>>n>>m;
	for(int i = 1; i <= m; i ++) cin>>u[i]>>v[i]>>d[i];
	cin>>q;
	for(int i = 1; i <= q; i ++) {
		cin>>t[i]>>x[i]>>y[i];
	}
	for(int l = 1; l <= q; l += B) {
		unchanged.clear(), ask.clear(), change.clear();
		for(int i = 1; i <= n; i ++) {
			par[i] = i;
			siz[i] = 1;
		}
		for(int i = 1; i <= m; i ++) changed[i] = 0;
		int r = min(q, l + B - 1);
		for(int i = l; i <= r; i ++) {
			if(t[i] == 1) changed[x[i]] = 1;
			else ask.pb(i);
		}
		for(int i = 1; i <= m; i ++) {
			if(!changed[i]) unchanged.pb(i);
			else change.pb(i);
		}
		for(int i = l; i <= r; i ++) {
			if(t[i] == 2) {
				for(auto p : change) if(d[p] >= y[i]) ex[i].pb(p);
			} else d[x[i]] = y[i];
		}
		sort(all(unchanged), [](int i, int j) {
			return d[i] < d[j];
		});
		sort(all(ask), [](int i, int j) {
			return y[i] > y[j];
		});
		for(auto i : ask) {
			while(!unchanged.empty() && d[unchanged.back()] >= y[i]) {
//				cout<<i<<" "<<unchanged.back()<<"\n";
				combine(u[unchanged.back()], v[unchanged.back()]);
				unchanged.pop_back();
			}
			// add the extra bridges which we changed in this block so they are a special case
			int prev = dat.size();
			for(auto p : ex[i]) {
//				cout<<i<<" "<<p<<" yolo \n";
				combine(u[p], v[p]);
			}
			ans[i] = siz[findpar(x[i])];
//			cout<<i<<" "<<y[i]<<" "<<findpar(x[i])<<"\n";
			rollback(prev);
		}
	}
	for(int i = 1; i <= q; i ++) if(t[i] == 2) cout<<ans[i]<<"\n";
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;
 
    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:50:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |  while(dat.size() > s) {
      |        ~~~~~~~~~~~^~~
bridges.cpp: In function 'void Freopen(std::string)':
bridges.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 22 ms 8280 KB Output is correct
4 Correct 4 ms 4952 KB Output is correct
5 Correct 12 ms 6492 KB Output is correct
6 Correct 10 ms 6644 KB Output is correct
7 Correct 11 ms 6492 KB Output is correct
8 Correct 12 ms 6236 KB Output is correct
9 Correct 10 ms 7516 KB Output is correct
10 Correct 9 ms 6420 KB Output is correct
11 Correct 12 ms 6232 KB Output is correct
12 Correct 10 ms 7000 KB Output is correct
13 Correct 16 ms 6808 KB Output is correct
14 Correct 13 ms 6496 KB Output is correct
15 Correct 10 ms 6500 KB Output is correct
16 Correct 9 ms 6748 KB Output is correct
17 Correct 12 ms 6748 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1109 ms 149236 KB Output is correct
2 Correct 1105 ms 149040 KB Output is correct
3 Correct 1220 ms 148876 KB Output is correct
4 Correct 1077 ms 148648 KB Output is correct
5 Correct 1088 ms 149016 KB Output is correct
6 Correct 1207 ms 206092 KB Output is correct
7 Correct 1164 ms 207332 KB Output is correct
8 Correct 1173 ms 206344 KB Output is correct
9 Correct 25 ms 6748 KB Output is correct
10 Correct 574 ms 180532 KB Output is correct
11 Correct 586 ms 164296 KB Output is correct
12 Correct 993 ms 136484 KB Output is correct
13 Correct 961 ms 145292 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 786 ms 140396 KB Output is correct
2 Correct 365 ms 95656 KB Output is correct
3 Correct 778 ms 162940 KB Output is correct
4 Correct 759 ms 140600 KB Output is correct
5 Correct 26 ms 6736 KB Output is correct
6 Correct 806 ms 150528 KB Output is correct
7 Correct 708 ms 135024 KB Output is correct
8 Correct 688 ms 126380 KB Output is correct
9 Correct 645 ms 120604 KB Output is correct
10 Correct 628 ms 117112 KB Output is correct
11 Correct 621 ms 120652 KB Output is correct
12 Correct 595 ms 116008 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1971 ms 107920 KB Output is correct
2 Correct 26 ms 6996 KB Output is correct
3 Correct 194 ms 8416 KB Output is correct
4 Correct 78 ms 8408 KB Output is correct
5 Correct 943 ms 108832 KB Output is correct
6 Correct 1892 ms 110396 KB Output is correct
7 Correct 969 ms 108952 KB Output is correct
8 Correct 902 ms 109488 KB Output is correct
9 Correct 894 ms 108652 KB Output is correct
10 Correct 889 ms 107744 KB Output is correct
11 Correct 1457 ms 109228 KB Output is correct
12 Correct 1388 ms 110432 KB Output is correct
13 Correct 1457 ms 110444 KB Output is correct
14 Correct 838 ms 109348 KB Output is correct
15 Correct 887 ms 109612 KB Output is correct
16 Correct 1980 ms 111012 KB Output is correct
17 Correct 1967 ms 110104 KB Output is correct
18 Correct 1958 ms 110676 KB Output is correct
19 Correct 1939 ms 111728 KB Output is correct
20 Correct 1658 ms 110156 KB Output is correct
21 Correct 1665 ms 109356 KB Output is correct
22 Correct 1873 ms 110880 KB Output is correct
23 Correct 1077 ms 108832 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1109 ms 149236 KB Output is correct
2 Correct 1105 ms 149040 KB Output is correct
3 Correct 1220 ms 148876 KB Output is correct
4 Correct 1077 ms 148648 KB Output is correct
5 Correct 1088 ms 149016 KB Output is correct
6 Correct 1207 ms 206092 KB Output is correct
7 Correct 1164 ms 207332 KB Output is correct
8 Correct 1173 ms 206344 KB Output is correct
9 Correct 25 ms 6748 KB Output is correct
10 Correct 574 ms 180532 KB Output is correct
11 Correct 586 ms 164296 KB Output is correct
12 Correct 993 ms 136484 KB Output is correct
13 Correct 961 ms 145292 KB Output is correct
14 Correct 786 ms 140396 KB Output is correct
15 Correct 365 ms 95656 KB Output is correct
16 Correct 778 ms 162940 KB Output is correct
17 Correct 759 ms 140600 KB Output is correct
18 Correct 26 ms 6736 KB Output is correct
19 Correct 806 ms 150528 KB Output is correct
20 Correct 708 ms 135024 KB Output is correct
21 Correct 688 ms 126380 KB Output is correct
22 Correct 645 ms 120604 KB Output is correct
23 Correct 628 ms 117112 KB Output is correct
24 Correct 621 ms 120652 KB Output is correct
25 Correct 595 ms 116008 KB Output is correct
26 Correct 1082 ms 147540 KB Output is correct
27 Correct 1183 ms 177368 KB Output is correct
28 Correct 1159 ms 146932 KB Output is correct
29 Correct 1010 ms 119004 KB Output is correct
30 Correct 1168 ms 162416 KB Output is correct
31 Correct 1185 ms 165504 KB Output is correct
32 Correct 1176 ms 166652 KB Output is correct
33 Correct 1118 ms 145924 KB Output is correct
34 Correct 1171 ms 145692 KB Output is correct
35 Correct 1163 ms 145960 KB Output is correct
36 Correct 1025 ms 122280 KB Output is correct
37 Correct 1004 ms 122392 KB Output is correct
38 Correct 1002 ms 121368 KB Output is correct
39 Correct 952 ms 111556 KB Output is correct
40 Correct 943 ms 111296 KB Output is correct
41 Correct 959 ms 110752 KB Output is correct
42 Correct 908 ms 108936 KB Output is correct
43 Correct 921 ms 109088 KB Output is correct
44 Correct 908 ms 109292 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 22 ms 8280 KB Output is correct
4 Correct 4 ms 4952 KB Output is correct
5 Correct 12 ms 6492 KB Output is correct
6 Correct 10 ms 6644 KB Output is correct
7 Correct 11 ms 6492 KB Output is correct
8 Correct 12 ms 6236 KB Output is correct
9 Correct 10 ms 7516 KB Output is correct
10 Correct 9 ms 6420 KB Output is correct
11 Correct 12 ms 6232 KB Output is correct
12 Correct 10 ms 7000 KB Output is correct
13 Correct 16 ms 6808 KB Output is correct
14 Correct 13 ms 6496 KB Output is correct
15 Correct 10 ms 6500 KB Output is correct
16 Correct 9 ms 6748 KB Output is correct
17 Correct 12 ms 6748 KB Output is correct
18 Correct 1109 ms 149236 KB Output is correct
19 Correct 1105 ms 149040 KB Output is correct
20 Correct 1220 ms 148876 KB Output is correct
21 Correct 1077 ms 148648 KB Output is correct
22 Correct 1088 ms 149016 KB Output is correct
23 Correct 1207 ms 206092 KB Output is correct
24 Correct 1164 ms 207332 KB Output is correct
25 Correct 1173 ms 206344 KB Output is correct
26 Correct 25 ms 6748 KB Output is correct
27 Correct 574 ms 180532 KB Output is correct
28 Correct 586 ms 164296 KB Output is correct
29 Correct 993 ms 136484 KB Output is correct
30 Correct 961 ms 145292 KB Output is correct
31 Correct 786 ms 140396 KB Output is correct
32 Correct 365 ms 95656 KB Output is correct
33 Correct 778 ms 162940 KB Output is correct
34 Correct 759 ms 140600 KB Output is correct
35 Correct 26 ms 6736 KB Output is correct
36 Correct 806 ms 150528 KB Output is correct
37 Correct 708 ms 135024 KB Output is correct
38 Correct 688 ms 126380 KB Output is correct
39 Correct 645 ms 120604 KB Output is correct
40 Correct 628 ms 117112 KB Output is correct
41 Correct 621 ms 120652 KB Output is correct
42 Correct 595 ms 116008 KB Output is correct
43 Correct 1971 ms 107920 KB Output is correct
44 Correct 26 ms 6996 KB Output is correct
45 Correct 194 ms 8416 KB Output is correct
46 Correct 78 ms 8408 KB Output is correct
47 Correct 943 ms 108832 KB Output is correct
48 Correct 1892 ms 110396 KB Output is correct
49 Correct 969 ms 108952 KB Output is correct
50 Correct 902 ms 109488 KB Output is correct
51 Correct 894 ms 108652 KB Output is correct
52 Correct 889 ms 107744 KB Output is correct
53 Correct 1457 ms 109228 KB Output is correct
54 Correct 1388 ms 110432 KB Output is correct
55 Correct 1457 ms 110444 KB Output is correct
56 Correct 838 ms 109348 KB Output is correct
57 Correct 887 ms 109612 KB Output is correct
58 Correct 1980 ms 111012 KB Output is correct
59 Correct 1967 ms 110104 KB Output is correct
60 Correct 1958 ms 110676 KB Output is correct
61 Correct 1939 ms 111728 KB Output is correct
62 Correct 1658 ms 110156 KB Output is correct
63 Correct 1665 ms 109356 KB Output is correct
64 Correct 1873 ms 110880 KB Output is correct
65 Correct 1077 ms 108832 KB Output is correct
66 Correct 1082 ms 147540 KB Output is correct
67 Correct 1183 ms 177368 KB Output is correct
68 Correct 1159 ms 146932 KB Output is correct
69 Correct 1010 ms 119004 KB Output is correct
70 Correct 1168 ms 162416 KB Output is correct
71 Correct 1185 ms 165504 KB Output is correct
72 Correct 1176 ms 166652 KB Output is correct
73 Correct 1118 ms 145924 KB Output is correct
74 Correct 1171 ms 145692 KB Output is correct
75 Correct 1163 ms 145960 KB Output is correct
76 Correct 1025 ms 122280 KB Output is correct
77 Correct 1004 ms 122392 KB Output is correct
78 Correct 1002 ms 121368 KB Output is correct
79 Correct 952 ms 111556 KB Output is correct
80 Correct 943 ms 111296 KB Output is correct
81 Correct 959 ms 110752 KB Output is correct
82 Correct 908 ms 108936 KB Output is correct
83 Correct 921 ms 109088 KB Output is correct
84 Correct 908 ms 109292 KB Output is correct
85 Correct 2181 ms 151672 KB Output is correct
86 Correct 241 ms 12840 KB Output is correct
87 Correct 96 ms 18124 KB Output is correct
88 Correct 1113 ms 164016 KB Output is correct
89 Correct 2138 ms 150812 KB Output is correct
90 Correct 1130 ms 163796 KB Output is correct
91 Correct 1126 ms 149792 KB Output is correct
92 Correct 1141 ms 150364 KB Output is correct
93 Correct 1234 ms 208124 KB Output is correct
94 Correct 1665 ms 151520 KB Output is correct
95 Correct 1646 ms 152032 KB Output is correct
96 Correct 1650 ms 207852 KB Output is correct
97 Correct 1018 ms 126620 KB Output is correct
98 Correct 1027 ms 130388 KB Output is correct
99 Correct 2188 ms 154012 KB Output is correct
100 Correct 2207 ms 152812 KB Output is correct
101 Correct 2175 ms 152988 KB Output is correct
102 Correct 2168 ms 152920 KB Output is correct
103 Correct 1871 ms 209232 KB Output is correct
104 Correct 1869 ms 209156 KB Output is correct
105 Correct 1739 ms 148120 KB Output is correct
106 Correct 1487 ms 128340 KB Output is correct
107 Correct 1710 ms 137048 KB Output is correct
108 Correct 2139 ms 179728 KB Output is correct
109 Correct 1291 ms 196180 KB Output is correct