Submission #1118673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118673		stefanneagu	Bridges (APIO19_bridges)	C++17	0 / 100	3045 ms	15172 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;
 
const int nmax = 1e5 + 1;
 
int nra = 1;
int bit[nmax];
 
int n, m;
int root[nmax], sz[nmax];
int mr[nmax], ms[nmax];
 
struct DSU {
 
  void init() {
    for(int i = 1; i <= n; i++) {
      root[i] = i;
      sz[i] = 1;
    }
  }
 
  int find(int a) {
    if(root[a] == a) {
      return a;
    }
    return root[a] = find(root[a]);
  }
 
  void unite(int a, int b) {
    if(a == b) {
      return;
    }
    if(sz[a] > sz[b]) {
      swap(a, b);
    }
    root[a] = b;
    sz[b] += sz[a];
  }
 
  int mfind(int a) {
    if(bit[a] != nra) {
      bit[a] = nra;
      mr[a] = find(a);
      ms[a] = sz[find(a)];
    }
    if(mr[a] == a) {
      return a;
    }
    return mr[a] = mfind(mr[a]);
  }
 
  void munite(int a, int b) {
    if(a == b) {
      return;
    }
    if(ms[a] > ms[b]) {
      swap(a, b);
    }
    mr[a] = b;
    ms[b] += ms[a];
  }
};
 
struct str {
	int a, b, c;
};
 
struct special {
  int t, a, b, c;
};
 
vector<str> qry, upd, edges;
vector<special> e2;
int ans[nmax], mark[nmax], to[nmax], ult[nmax];
int pas = 1;
 
bool cmp(special x, special y) {
  if(x.c != y.c) {
    return x.c > y.c;
  }
  return x.t < y.t;
}
 
bool cmp2(str x, str y) {
  return x.c < y.c;
}
 
bool cmp3(str x, str y) {
  return x.b > y.b;
}

void fun(vector<special> e2, vector<special> pen) {
  cout << "pen\n";
  for(auto it : pen) {
    cout << it.t << " " << it.a << " " << it.b << " " << it.c << '\n';
  }
  cout << "e2\n";
  for(auto it : e2) {
    cout << it.t << " " << it.a << " " << it.b << " " << it.c << '\n';
  }
  exit(0);
}
 
void solve() {
	vector<special> curr, doar;
	vector<pair<int, int>> unsafe;
	for(int i = 1; i <= m; i++) {
    if(mark[i] == pas) {
      unsafe.push_back({i, edges[i].c});
    }
	}
	// cout << "-------\n";
	sort(qry.begin(), qry.end(), cmp3);
	int ie = 0, iq = 0;
	while(ie < e2.size() || iq < qry.size()) {
	  while(ie < e2.size() && mark[e2[ie].t] == pas) {
	    ie++;
	  }
	  if(iq >= qry.size() || (ie < e2.size() && e2[ie].c >= qry[iq].b)) {
	    curr.push_back({0, e2[ie].a, e2[ie].b, e2[ie].c});
	    doar.push_back({e2[ie].t, e2[ie].a, e2[ie].b, e2[ie].c});
	    ie++;
	  } else {
	    curr.push_back({1, qry[iq].a, qry[iq].c, qry[iq].b});
	    iq++;
	  }
	}
	DSU ds;
	ds.init();
	for(auto [t, a, b, c] : curr) {
    if(t == 0) {
      ds.unite(ds.find(a), ds.find(b));
    } else {
      swap(b, c);
      for(auto it : upd) {
        if(it.c <= c) {
          edges[it.a].c = it.b;
        }
      }
      for(auto it : unsafe) {
        if(edges[it.first].c >= b) {
          ds.munite(ds.mfind(edges[it.first].a), ds.mfind(edges[it.first].b));
        }
        edges[it.first].c = it.second;
      }
      ans[c] = ms[ds.mfind(a)];
      nra++;
    }
	}
  pas++;
  sort(upd.begin(), upd.end(), cmp2);
  reverse(upd.begin(), upd.end());
  vector<special> up;
  for(auto [a, b, c] : upd) {
    if(ult[a] != pas) {
      ult[a] = pas;
      up.push_back({a, edges[a].a, edges[a].b, b});
      edges[a].c = b;
    }
  }
  sort(up.begin(), up.end(), cmp);
  int iu = 0, id = 0;
  e2.clear();
  assert(up.size() + doar.size() == m);
  while(iu < upd.size() || id < doar.size()) {
    if(id >= doar.size() || (iu < upd.size() && up[iu].c > doar[id].c)) {
      e2.push_back(up[iu]);
      iu++;
    } else {
      e2.push_back(doar[id]);
      id++;
    }
  }
  sort(e2.begin(), e2.end(), cmp);
  vector<special> pen;
  for(int i = 1; i <= m; i++) {
    pen.push_back({i, edges[i].a, edges[i].b, edges[i].c});
  }
  if(e2.size() != m) {
    while(true) {
      ///
    }
  }
  sort(pen.begin(), pen.end(), cmp);
  if(pen.size() != e2.size()) {
    fun(e2, pen);
    //assert(0);
  }
  for(int i = 0; i < e2.size(); i++) {
    if(e2[i].t != pen[i].t) {
      fun(e2, pen);
      //assert(0);
    }
    if(e2[i].a != pen[i].a) {
      fun(e2, pen);
      //assert(0);
    }
    if(e2[i].b != pen[i].b) {
      fun(e2, pen);
      //assert(0);
    }
    if(e2[i].c != pen[i].c) {
      fun(e2, pen);
      //assert(0);
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  edges.push_back({-1, -1, -1});
  for(int i = 1; i <= m; i++) {
    int a, b, c;
		cin >> a >> b >> c;
		if(a > b) {
			swap(a, b);
		}
		edges.push_back({a, b, c});
		e2.push_back({i, a, b, c});
  }
  sort(e2.begin(), e2.end(), cmp);
  for(int i = 0; i < m; i++) {
    to[e2[i].t] = i;
  }
  int q;
  cin >> q;
  int block = sqrt(q);
  for(int i = 1; i <= q; i++) {
    int t, a, b;
		cin >> t >> a >> b;
		if(t == 1) {
			// update
			mark[a] = pas;
			upd.push_back({a, b, i});
		} else {
			// query
			qry.push_back({a, b, i});
		}
		if(i % block == 0 || i == q) {
			solve();
			upd.clear();
			qry.clear();
		}
  }
  for(int i = 1; i <= q; i++) {
    if(ans[i] != 0) {
      cout << ans[i] << "\n";
		}
  }
  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:116:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  while(ie < e2.size() || iq < qry.size()) {
      |        ~~~^~~~~~~~~~~
bridges.cpp:116:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  while(ie < e2.size() || iq < qry.size()) {
      |                          ~~~^~~~~~~~~~~~
bridges.cpp:117:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |    while(ie < e2.size() && mark[e2[ie].t] == pas) {
      |          ~~~^~~~~~~~~~~
bridges.cpp:120:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    if(iq >= qry.size() || (ie < e2.size() && e2[ie].c >= qry[iq].b)) {
      |       ~~~^~~~~~~~~~~~~
bridges.cpp:120:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    if(iq >= qry.size() || (ie < e2.size() && e2[ie].c >= qry[iq].b)) {
      |                            ~~~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from bridges.cpp:1:
bridges.cpp:165:34: warning: comparison of integer expressions of different signedness: 'std::vector<special>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |   assert(up.size() + doar.size() == m);
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
bridges.cpp:166:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   while(iu < upd.size() || id < doar.size()) {
      |         ~~~^~~~~~~~~~~~
bridges.cpp:166:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   while(iu < upd.size() || id < doar.size()) {
      |                            ~~~^~~~~~~~~~~~~
bridges.cpp:167:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     if(id >= doar.size() || (iu < upd.size() && up[iu].c > doar[id].c)) {
      |        ~~~^~~~~~~~~~~~~~
bridges.cpp:167:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     if(id >= doar.size() || (iu < upd.size() && up[iu].c > doar[id].c)) {
      |                              ~~~^~~~~~~~~~~~
bridges.cpp:180:16: warning: comparison of integer expressions of different signedness: 'std::vector<special>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  180 |   if(e2.size() != m) {
      |      ~~~~~~~~~~^~~~
bridges.cpp:190:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |   for(int i = 0; i < e2.size(); i++) {
      |                  ~~^~~~~~~~~~~

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