#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll mod = 1e9 + 7;
const ll N = 2e5 + 37;
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
const ll inf = (ll)1e9 + 37;
using aaa = array<ll, 3>;
ll n, m, Q;
vector<vector<array<ll, 3> > > g;
vector<bool> vis;
ll ans = 0, car = -1;
vector<ll> change;
void brute_dfs(ll v) {
if(vis[v]) {
return;
}
++ans;
vis[v] = true;
for(auto& a : g[v]) {
a[1] = change[a[2]];
if(car <= a[1] and !vis[a[0]]) {
brute_dfs(a[0]);
}
}
}
void brute() {
while(Q--) {
ans = 0;
ll qt;
cin >> qt;
if(qt == 1) {
ll idx, w;
cin >> idx >> w;
change[idx] = w;
}
else if(qt == 2) {
ll u;
cin >> u >> car;
vis.assign(n + 1, false);
brute_dfs(u);
// cout << u << ' ' << car << ' ' << vis << " : " << ans << endl;
cout << ans << endl;
}
else assert(false);
}
}
void line() {
vector<ll> tree(2 * m + 3);
auto update = [&](ll idx, ll val) -> void
{
for (tree[idx += m] = val; idx > 1; idx >>= 1) tree[idx>>1] = min(tree[idx], tree[idx^1]);
};
auto query = [&](ll l, ll r) -> ll
{
ll res = inf;
for (l += m, r += m; l <= r; l >>= 1, r >>= 1) {
if (l&1) res = min(res, tree[l++]);
if ((r&1)^1) res = min(res,tree[r--]);
}
return res;
};
assert(m == n - 1);
for(ll i = 1; i <= m; ++i) {
update(i, change[i]);
}
while(Q--) {
ll qt;
cin >> qt;
if(qt == 1) {
ll idx, w;
cin >> idx >> w;
update(idx, w);
}
else if(qt == 2) {
ll u, w;
cin >> u >> w;
ll l = 1, r = u - 1, l_ans = u, r_ans = u;
while(l <= r) {
ll mid = (l + r) / 2;
if(query(mid, u-1) >= w) {
r = mid - 1;
l_ans = mid;
}
else {
l = mid + 1;
}
}
l = u, r = n - 1;
while(l <= r) {
ll mid = (l + r) / 2;
if(query(u, mid) >= w) {
r_ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << r_ans - l_ans + 1 << endl;
}
else assert(false);
}
}
void solve() {
cin >> n >> m;
g.assign(n + 1, vector<aaa>());
change.assign(m + 1, -1);
vis.assign(n + 1, false);
for(ll i = 1; i <= m; ++i) {
ll u, v, c;
cin >> u >> v >> c;
g[u].pb({v, c, i});
g[v].pb({u, c, i});
change[i] = c;
}
cin >> Q;
if(n <= 1000 and m <= 1000 and Q <= 10'000) {
brute();
return;
}
line();
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// signed t; cin >> t; while(t--)
solve();
}
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
os << "[";
for(size_t i = 0; i + 1 < N; ++i) {
os << a[i] << ", ";
}
if(N > 0)
os << a[N - 1];
os << "]";
return os;
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
os << "(" << p.first << ", " << p.second << ") ";
return os;
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
os << '[';
for(auto x : v)
os << x << ", ";
os << "] ";
return os;
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
os << "{";
for(auto x : s)
os << x << ", ";
os << "} ";
return os;
}
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
os << "{";
for(auto x : s)
os << x << ", ";
os << "} ";
return os;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
5212 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
