Submission #1004987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004987		vjudge1	Bridges (APIO19_bridges)	C++17	0 / 100	3065 ms	21208 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
set<pair<int,int> > G[N];
vector<vector<int> > e;
bool seen[N];

void dfs(int v, int w)
{
  seen[v] = true;
  for(auto [u, ew] : G[v])
    if(w <= ew && !seen[u])
      dfs(u, w);
}

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i = 0; i < m; i ++)
    {
      int u, v, w;
      cin >> u >> v >> w;
      G[u].insert({v, w});
      G[v].insert({u, w});
      e.push_back({u, v, w});
    }

  int q;
  cin >> q;
  while(q--)
    {
      int t, x, y;
      cin >> t >> x >> y;
      if(t == 1)
	{
	  x--;
	  int u = e[x][0], v = e[x][1], w = e[x][2];
	  G[u].erase({v, w});
	  G[v].erase({u, w});
	  w = e[x][2] = y;
	  G[u].insert({v, w});
	  G[v].insert({u, w});
	}
      else
	{
	  dfs(x, y);
	  int ans = 0;
	  for(int i = 1; i <= n; i ++)
	    ans += seen[i], seen[i] = false;
	  cout << ans << endl;
	}
    }
  
  return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27