이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e4 + 5;
set<array<int, 2> > g[N];
vector<bool> vis(N);
int dfs(int node, int wt, int par)
{
vis[node] = true;
int ans = 1;
for(auto [to, cur_wt]: g[node])
{
if(cur_wt >= wt && !vis[to])
{
ans += dfs(to, wt, node);
}
}
return ans;
}
void Solve()
{
int n, m;
cin >> n >> m;
vector<array<int, 3> > edges(m + 1);
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].insert({v, w});
g[v].insert({u, w});
edges[i] = {u, v, w};
}
int q;
cin >> q;
for(int i = 1; i <= q; i++)
{
int command;
cin >> command;
if(command == 1)
{
int edge_idx, wt;
cin >> edge_idx >> wt;
int prev_wt = edges[edge_idx][2];
int u = edges[edge_idx][0], v = edges[edge_idx][1];
g[u].erase({v, prev_wt});
g[u].insert({v, wt});
g[v].erase({u, prev_wt});
g[v].insert({u, wt});
edges[edge_idx][2] = wt;
}
else
{
int node, start_wt;
cin >> node >> start_wt;
for(int i = 0; i <= n; i++)
{
vis[i] = false;
}
// cout << "hello\n";
// cout << "node = " << node << ", start_wt = " << start_wt << "\n";
cout << dfs(node, start_wt, -1) << "\n";
}
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |