#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e5+5;
vector< vector< pair<int, int> > > adj(MAXN);
vector< pair<int, pair<int, int> > > edges;
vector<bool> visited(MAXN);
int par[MAXN], sz[MAXN];
int find(int v)
{
if(par[v] == v)
return v;
return par[v] = find(par[v]);
}
void merge(int a, int b)
{
a = find(a), b = find(b);
if(a == b)
return;
if(sz[a] < sz[b])
swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
int dfs(int v, int weight, int p)
{
int ans = 1;
visited[v] = true;
for(pair<int, int> e : adj[v])
{
if(visited[e.first] || e.second < weight)
continue;
ans += dfs(e.first, weight, v);
}
return ans;
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int f, s, w;
cin >> f >> s >> w;
adj[f].push_back({s, w});
adj[s].push_back({f, w});
edges.push_back({w, {f, s}});
}
int q;
cin >> q;
if(max(m, n) <= 1000 && q <= 10000) // Subtask 1
{
for(int i = 1; i <= q; i++)
{
int f, s, t;
cin >> f >> s >> t;
if(f == 1)
{
s--;
int from = edges[s].second.first, to = edges[s].second.second;
for(int l = 0; l < adj[from].size(); l++)
{
if(adj[from][l].first == to && adj[from][l].second == edges[s].first) {
adj[from][l].second = t;
break;
}
}
for(int l = 0; l < adj[to].size(); l++)
{
if(adj[to][l].first == from && adj[to][l].second == edges[s].first) {
adj[to][l].second = t;
break;
}
}
edges[s].first = t;
} else
{
for(int i = 0; i <= n; i++)
visited[i] = false;
int ans = dfs(s, t, -1);
cout << ans << "\n";
}
}
} else //Subtask 4
{
for(int i = 1; i <= n; i++)
{
sz[i] = 1;
par[i] = i;
}
sort(edges.begin(), edges.end());
reverse(edges.begin(), edges.end());
int idx = 0;
vector< pair<int, pair<int, int> > > queries;
vector<int> ans(q+5, 0);
for(int i = 1; i <= q; i++)
{
int f, s, t;
cin >> f >> s >> t;
queries.push_back({t, {s, i}});
}
sort(queries.begin(), queries.end());
reverse(queries.begin(), queries.end());
for(int i = 0; i < q; i++)
{
while(idx < m && edges[idx].first >= queries[i].first)
{
merge(edges[idx].second.first, edges[idx].second.second);
idx++;
}
ans[queries[i].second.second] = sz[find(queries[i].second.first)];
}
for(int i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:62:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int l = 0; l < adj[from].size(); l++)
| ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:69:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int l = 0; l < adj[to].size(); l++)
| ~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
47 ms |
2732 KB |
Output is correct |
4 |
Correct |
20 ms |
2644 KB |
Output is correct |
5 |
Correct |
17 ms |
2696 KB |
Output is correct |
6 |
Correct |
18 ms |
2680 KB |
Output is correct |
7 |
Correct |
15 ms |
2644 KB |
Output is correct |
8 |
Correct |
22 ms |
2696 KB |
Output is correct |
9 |
Correct |
17 ms |
2644 KB |
Output is correct |
10 |
Correct |
20 ms |
2644 KB |
Output is correct |
11 |
Correct |
18 ms |
2700 KB |
Output is correct |
12 |
Correct |
17 ms |
2696 KB |
Output is correct |
13 |
Correct |
19 ms |
2704 KB |
Output is correct |
14 |
Correct |
18 ms |
2644 KB |
Output is correct |
15 |
Correct |
20 ms |
2644 KB |
Output is correct |
16 |
Correct |
15 ms |
2700 KB |
Output is correct |
17 |
Correct |
16 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
152 ms |
8664 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
140 ms |
7936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
201 ms |
11196 KB |
Output is correct |
2 |
Correct |
82 ms |
5820 KB |
Output is correct |
3 |
Correct |
99 ms |
8012 KB |
Output is correct |
4 |
Correct |
103 ms |
8220 KB |
Output is correct |
5 |
Correct |
165 ms |
12184 KB |
Output is correct |
6 |
Correct |
213 ms |
13436 KB |
Output is correct |
7 |
Correct |
161 ms |
12180 KB |
Output is correct |
8 |
Correct |
150 ms |
9772 KB |
Output is correct |
9 |
Correct |
152 ms |
9856 KB |
Output is correct |
10 |
Correct |
141 ms |
9896 KB |
Output is correct |
11 |
Correct |
176 ms |
12088 KB |
Output is correct |
12 |
Correct |
180 ms |
12204 KB |
Output is correct |
13 |
Correct |
178 ms |
11952 KB |
Output is correct |
14 |
Correct |
161 ms |
12220 KB |
Output is correct |
15 |
Correct |
164 ms |
12164 KB |
Output is correct |
16 |
Correct |
204 ms |
12884 KB |
Output is correct |
17 |
Correct |
205 ms |
12780 KB |
Output is correct |
18 |
Correct |
212 ms |
13092 KB |
Output is correct |
19 |
Correct |
205 ms |
13056 KB |
Output is correct |
20 |
Correct |
181 ms |
12160 KB |
Output is correct |
21 |
Correct |
188 ms |
12240 KB |
Output is correct |
22 |
Correct |
196 ms |
12632 KB |
Output is correct |
23 |
Correct |
146 ms |
10880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
152 ms |
8664 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
47 ms |
2732 KB |
Output is correct |
4 |
Correct |
20 ms |
2644 KB |
Output is correct |
5 |
Correct |
17 ms |
2696 KB |
Output is correct |
6 |
Correct |
18 ms |
2680 KB |
Output is correct |
7 |
Correct |
15 ms |
2644 KB |
Output is correct |
8 |
Correct |
22 ms |
2696 KB |
Output is correct |
9 |
Correct |
17 ms |
2644 KB |
Output is correct |
10 |
Correct |
20 ms |
2644 KB |
Output is correct |
11 |
Correct |
18 ms |
2700 KB |
Output is correct |
12 |
Correct |
17 ms |
2696 KB |
Output is correct |
13 |
Correct |
19 ms |
2704 KB |
Output is correct |
14 |
Correct |
18 ms |
2644 KB |
Output is correct |
15 |
Correct |
20 ms |
2644 KB |
Output is correct |
16 |
Correct |
15 ms |
2700 KB |
Output is correct |
17 |
Correct |
16 ms |
2644 KB |
Output is correct |
18 |
Incorrect |
152 ms |
8664 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |