이 제출은 이전 버전의 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;
vector<array<int, 2> > g[N];
vector<array<int, 3> > edges(N * 2);
vector<bool> vis(N);
int dfs(int node, int wt)
{
vis[node] = true;
int ans = 1;
for(auto [to, idx]: g[node])
{
int cur_wt = edges[idx][2];
if(cur_wt >= wt && !vis[to])
{
ans += dfs(to, wt);
}
}
return ans;
}
void Solve()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, i});
g[v].push_back({u, i});
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;
edges[edge_idx][2] = wt;
}
else
{
int node, start_wt;
cin >> node >> start_wt;
for(int j = 0; j <= n; j++)
{
vis[j] = false;
}
// cout << "hello\n";
// cout << "node = " << node << ", start_wt = " << start_wt << "\n";
cout << dfs(node, start_wt) << "\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... |