제출 #1005065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005065		vjudge1	다리 (APIO19_bridges)	C++17	27 / 100	290 ms	31344 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int N = 5e4+5, M = 1e5+5, K = 20;
multiset<pair<int,int> > G[N];
vector<vector<int> > e, p, Q;
int ans[M], par[N], sz[N], n, m, q;
bool seen[N];

void subtask1();
void subtask2();
void subtask4();

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  

  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});
    }

  cin >> q;
  bool s2 = true;
  for(int i = 0; i < q; i ++)
    {
      int t, x, y;
      cin >> t >> x >> y;
      s2 &= t - 1;
      Q.push_back({t, x, y});
    }
  
  if(n <= 1000 && m <= 1000 && q <= 10000)
      subtask1();
  else if(s2)
    subtask4();
  else
    subtask2();
  return 0;
}

int seg[2 << 16];

void modify(int p, int d, int s = 0, int e = N, int v = 1)
{
  if(p < s || e <= p) return;
  if(e - s == 1)
    {
      seg[v] = d;
      return;
    }

  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  modify(p, d, s, mid, lc);
  modify(p, d, mid, e, rc);
  seg[v] = min(seg[lc], seg[rc]); 
}

int get(int l, int r, int s = 0, int e = N, int v = 1)
{
  if(r <= s || e <= l) return INT_MAX;
  if(l <= s && e <= r) return seg[v];
  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  return min(get(l, r, s, mid, lc), get(l, r, mid, e, rc));
}

void subtask2()
{
  for(auto ed : e)
    modify(ed[0], ed[1]);

  for(auto qy : Q)
    {
      if(qy[0] == 1)
	modify(qy[1], qy[2]);
      else
	{
	  int s = qy[1], e = qy[1], w = qy[2];
	  for(int i = K - 1; i >= 0; i--)
	    if(e + (1 << i) <= n && get(e, e + (1 << i)) >= w)
	      e += (1 << i);
	  for(int i = K - 1; i >= 0; i--)
	    if(s - (1 << i) >= 1 && get(s - (1 << i), s) >= w)
	      s -= (1 << i);
	  cout << e - s + 1 << '\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 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 subtask4()
{
  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]);
  int i = 0;
  for(auto qy : Q)
    {
      int t = qy[0], x = qy[1], y = qy[2];
      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 < m && 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';
}

void subtask1()
{
  for(auto qy : Q)
    {
      int t = qy[0], x = qy[1], y = qy[2];
      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 << '\n';
	}
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'void subtask4()':
bridges.cpp:146:11: warning: unused variable 't' [-Wunused-variable]
  146 |       int t = qy[0], x = qy[1], y = qy[2];
      |           ^
bridges.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for(int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~

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