Submission #1005023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005023		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3009 ms	27644 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

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

int root(int x)
{
  if(par[x] == x) return x;
  return par[x] = root(par[x]);
}

void merge(int a, int b)
{
  a = root(a), b = root(b);
  if(a == b) return;
  if(sz[a] > sz[b]) swap(a,  b);
  par[a] = b;
  sz[b] += sz[a];
}

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()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  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;
  if(n <= 1000 && q <= 10000)
    {
      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;
    }


  for(int i = 1; i <= n; i ++)
    par[i] = i, sz[i] = 1;
  
  for(int i = 0; i < m; i ++)
    swap(e[i][0], e[i][2]);
  
  for(int i = 0; i < q; i ++)
    {
      int t, x, y;
      cin >> t >> x >> y;
      p.push_back({y, x, i});
    }

  sort(e.rbegin(), e.rend());
  sort(p.rbegin(), p.rend());

  int j = 0;
  for(int i = 0; i < p.size(); i++)
    {
      while(j < e.size() && e[j][0] >= p[i][0])
	{
	  merge(e[j][1], e[j][2]);
	  j++;
	}
      ans[p[i][2]] = sz[root(p[i][1])];
    }
  
  
  
  for(int i = 0; i < q; i ++)
    cout << ans[i] << '\n';
  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
bridges.cpp:100:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |       while(j < e.size() && e[j][0] >= p[i][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