#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 1e5 + 7;
int n, m, q, s[N], t[N], wt[N], it[2 * N], pset[N], ans[N];
bool sub2 = true, vis[N];
int type, a, b;
vector < pair < int, pair <int, int> > > query, ed;
vector < pair <int, int> > edge[N];
void init(int k, int l, int r){
if(l == r){
it[k] = wt[l];
return;
}
int mid = (l + r) >> 1;
init(k << 1, l, mid);
init(k << 1 | 1, mid + 1, r);
it[k] = min(it[k << 1], it[k << 1 | 1]);
}
void update(int k, int l, int r, int pos, int val){
if(l > pos || r < pos) return;
if(l == r){
it[k] = val;
return;
}
int mid = (l + r) >> 1;
update(k << 1, l, mid, pos, val);
update(k << 1 | 1, mid + 1, r, pos, val);
it[k] = min(it[k << 1], it[k << 1 | 1]);
}
int get(int k, int l, int r, int L, int R){
if(l > R || r < L || L > R) return (int)1e9;
if(l >= L && r <= R) return it[k];
int mid = (l + r) >> 1;
return min(get(k << 1, l, mid, L, R), get(k << 1 | 1, mid + 1, r, L, R));
}
int fset(int x){
if(pset[x] < 0) return x;
return pset[x] = fset(pset[x]);
}
void unionset(int x, int y){
x = fset(x), y = fset(y);
if(x == y) return;
pset[x] += pset[y];
pset[y] = x;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
if(m != n - 1) sub2 = false;
for(int i = 1; i <= m; i++){
cin >> s[i] >> t[i] >> wt[i];
if(s[i] != i || t[i] != i + 1) sub2 = false;
}
cin >> q;
if(n <= 1000 && m <= 1000 && q <= 10000){
for(int i = 1; i <= q; i++){
cin >> type >> a >> b;
if(type == 1) wt[a] = b;
else{
for(int i = 1; i <= n; i++) edge[i].clear(), vis[i] = false;
for(int i = 1; i <= m; i++){
edge[s[i]].pb(mp(t[i], wt[i]));
edge[t[i]].pb(mp(s[i], wt[i]));
}
int ans = 0;
vis[a] = true;
queue <int> q;
q.push(a);
while(!q.empty()){
int u = q.front();
q.pop();
ans++;
for(int i = 0; i < (int)edge[u].size(); i++){
int v = edge[u][i].fi, w = edge[u][i].se;
if(b > w || vis[v]) continue;
q.push(v);
vis[v] = true;
}
}
cout << ans << "\n";
}
}
return 0;
}
else if(sub2){
init(1, 1, m);
for(int i = 1; i <= q; i++){
cin >> type >> a >> b;
if(type == 1){
wt[a] = b;
update(1, 1, m, a, b);
}
else{
int lef = a, rig = a;
if(a > 1 && wt[a - 1] >= b){
int l = 1, r = a - 1, mid = (l + r) >> 1;
while(l < r){
if(get(1, 1, m, mid, a - 1) >= b) r = mid;
else l = mid + 1;
mid = (l + r) >> 1;
}
lef = l;
}
if(a < n && wt[a] >= b){
int l = a + 1, r = n, mid = (l + r + 1) >> 1;
while(l < r){
if(get(1, 1, m, a, mid - 1) >= b) l = mid;
else r = mid - 1;
mid = (l + r + 1) >> 1;
}
rig = l;
}
cout << rig - lef + 1 << "\n";
}
}
return 0;
}
else{
for(int i = 1; i <= q; i++){
cin >> type >> a >> b;
query.pb(mp(-b, mp(a, i)));
}
for(int i = 1; i <= m; i++){
ed.pb(mp(-wt[i], mp(s[i], t[i])));
}
for(int i = 1; i <= n; i++) pset[i] = -1;
sort(query.begin(), query.end());
sort(ed.begin(), ed.end());
int now = 0;
for(int i = 0; i < (int)query.size(); i++){
int id = query[i].se.se;
int u = query[i].se.fi;
int w = -query[i].fi;
while(now < m && -ed[now].fi >= w){
unionset(ed[now].se.fi, ed[now].se.se);
now++;
}
ans[id] = -pset[fset(u)];
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
150 ms |
2848 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
18 ms |
2772 KB |
Output is correct |
6 |
Correct |
17 ms |
2812 KB |
Output is correct |
7 |
Correct |
19 ms |
2780 KB |
Output is correct |
8 |
Correct |
17 ms |
2772 KB |
Output is correct |
9 |
Correct |
18 ms |
2772 KB |
Output is correct |
10 |
Correct |
16 ms |
2772 KB |
Output is correct |
11 |
Correct |
16 ms |
2772 KB |
Output is correct |
12 |
Correct |
17 ms |
2772 KB |
Output is correct |
13 |
Correct |
25 ms |
2772 KB |
Output is correct |
14 |
Correct |
26 ms |
2772 KB |
Output is correct |
15 |
Correct |
22 ms |
2772 KB |
Output is correct |
16 |
Correct |
16 ms |
2772 KB |
Output is correct |
17 |
Correct |
16 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
217 ms |
6540 KB |
Output is correct |
2 |
Correct |
245 ms |
6528 KB |
Output is correct |
3 |
Correct |
216 ms |
6620 KB |
Output is correct |
4 |
Correct |
207 ms |
6644 KB |
Output is correct |
5 |
Correct |
242 ms |
6584 KB |
Output is correct |
6 |
Correct |
425 ms |
6648 KB |
Output is correct |
7 |
Correct |
433 ms |
6620 KB |
Output is correct |
8 |
Correct |
412 ms |
6604 KB |
Output is correct |
9 |
Runtime error |
335 ms |
524288 KB |
Execution killed with signal 9 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
73 ms |
8148 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
11064 KB |
Output is correct |
2 |
Runtime error |
243 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
217 ms |
6540 KB |
Output is correct |
2 |
Correct |
245 ms |
6528 KB |
Output is correct |
3 |
Correct |
216 ms |
6620 KB |
Output is correct |
4 |
Correct |
207 ms |
6644 KB |
Output is correct |
5 |
Correct |
242 ms |
6584 KB |
Output is correct |
6 |
Correct |
425 ms |
6648 KB |
Output is correct |
7 |
Correct |
433 ms |
6620 KB |
Output is correct |
8 |
Correct |
412 ms |
6604 KB |
Output is correct |
9 |
Runtime error |
335 ms |
524288 KB |
Execution killed with signal 9 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
150 ms |
2848 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
18 ms |
2772 KB |
Output is correct |
6 |
Correct |
17 ms |
2812 KB |
Output is correct |
7 |
Correct |
19 ms |
2780 KB |
Output is correct |
8 |
Correct |
17 ms |
2772 KB |
Output is correct |
9 |
Correct |
18 ms |
2772 KB |
Output is correct |
10 |
Correct |
16 ms |
2772 KB |
Output is correct |
11 |
Correct |
16 ms |
2772 KB |
Output is correct |
12 |
Correct |
17 ms |
2772 KB |
Output is correct |
13 |
Correct |
25 ms |
2772 KB |
Output is correct |
14 |
Correct |
26 ms |
2772 KB |
Output is correct |
15 |
Correct |
22 ms |
2772 KB |
Output is correct |
16 |
Correct |
16 ms |
2772 KB |
Output is correct |
17 |
Correct |
16 ms |
2772 KB |
Output is correct |
18 |
Correct |
217 ms |
6540 KB |
Output is correct |
19 |
Correct |
245 ms |
6528 KB |
Output is correct |
20 |
Correct |
216 ms |
6620 KB |
Output is correct |
21 |
Correct |
207 ms |
6644 KB |
Output is correct |
22 |
Correct |
242 ms |
6584 KB |
Output is correct |
23 |
Correct |
425 ms |
6648 KB |
Output is correct |
24 |
Correct |
433 ms |
6620 KB |
Output is correct |
25 |
Correct |
412 ms |
6604 KB |
Output is correct |
26 |
Runtime error |
335 ms |
524288 KB |
Execution killed with signal 9 |
27 |
Halted |
0 ms |
0 KB |
- |