Submission #1005004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005004		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3054 ms	21240 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

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

void dfs(int v, int w)
{
  seen[v] = true;
  for(auto it = G[v].begin(); it != G[v].end(); it++)
    if(it -> second >= w && !seen[it -> first])
      dfs(it->first, 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(G[u].find({v, w}));
	  G[v].erase(G[v].find({u, w}));
	  w = e[x][2] = y;
	  G[u].insert({v, w});
	  G[v].insert({u, w});
	}
      else if(t == 2)
	{
	  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: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27