Submission #1118611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118611		stefanneagu	Bridges (APIO19_bridges)	C++17	0 / 100	571 ms	18900 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e4 + 1;

int nra = 1;
int lot[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(lot[a] != nra) {
      lot[a] = nra;
      mr[a] = find(a);
      ms[a] = sz[find(a)];
      // cout << "? " << a << " " << mr[a] << " " << ms[a] << '\n';
    }
    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, i;
};

struct EDG2 {
  int a, b, c, i;
};

vector<str> qry, upd, edges;
vector<EDG2> edg2;
vector<pair<int, int>> unsafe;
int ans[nmax], mark[nmax], to[nmax], fn[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 cmpedg2(EDG2 x, EDG2 y) {
  return x.c > y.c;
}

bool dupa_b(str x, str y) {
    return x.b > y.b;
}

void solve() {
  //cout << "START\n";
  sort(qry.begin(), qry.end(), dupa_b);
	vector<special> curr;
	//cout << qry.size() << " " << edg2.size() << '\n';
	int iq = 0, ie = 0;
	while(iq < qry.size() || ie < edg2.size()) {
    if(ie == edg2.size() || qry[iq].b > edg2[ie].c) {
      //cout << "Q";
      // cout << qry[iq].b << '\n';
      curr.push_back({1, qry[iq].a, qry[iq].b, qry[iq].c, -1});
      iq++;
    } else {
      if(mark[edg2[ie].i] != pas) {
        //cout << "U";
        // cout << edg2[ie].c << '\n';
        curr.push_back({0, edg2[ie].a, edg2[ie].b, edg2[ie].c, edg2[ie].i});
      }
      ie++;
    }
	}
	DSU ds;
	ds.init();
	for(auto _ : curr) {
    int t = _.t, a = _.a, b = _.b, c = _.c;
    // cout << "! " << t << " " << a << " " << b << " " << c << '\n';
    if(t == 0) {
      // unite
      ds.unite(ds.find(a), ds.find(b));
    } else {
      // query
      // cout << a << " " << b << '\n';
      for(auto it : upd) {
        if(it.c <= c) {
          edges[it.a].c = it.b;
        }
      }
      for(auto it : unsafe) {
        if(edges[it.first].c >= b) {
          // cout << "xtra: " << edges[it.first].a << " " << edges[it.first].b << " " << edges[it.first].c << '\n';
          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++;
      // cout << ans[c] << '\n';
    }
	}
  pas++;
  sort(upd.begin(), upd.end(), cmp2);
  reverse(upd.begin(), upd.end());
  vector<EDG2> v;
  for(auto it : upd) {
    if(fn[it.a] != nra) {
      fn[it.a] = nra;
      v.push_back({edges[it.a].a, edges[it.a].b, it.b, it.a});
    }
  }
  int iv = 0, ic = 0;
  vector<EDG2> nou;
  while(iv < v.size() || ic < curr.size()) {
    // break;
    while(ic < curr.size() && curr[ic].t == 1) {
      ic++;
    }
    if(ic >= curr.size() || (iv < v.size() && v[iv].c >= curr[ic].c)) {
      nou.push_back(v[iv]);
      iv++;
    } else {
      nou.push_back({curr[ic].a, curr[ic].b, curr[ic].c, curr[ic].i});
      ic++;
    }
  }
  swap(nou, edg2);
}

int get_to(int val) {
  int l = 0, r = edg2.size(), ans = 0;
  while(l <= r) {
    int mid = (l + r) / 2;
    if(edg2[mid].c <= val) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return ans;
}

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});
		edg2.push_back({a, b, c, i});
  }
  sort(edg2.begin(), edg2.end(), cmpedg2);
  for(int i = 1; i <= m; i++) {
    to[i] = get_to(edges[i].c);
  }
  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
			if(mark[a] != pas) {
        unsafe.push_back({a, edges[a].c});
			}
			mark[a] = pas;
			// cout << ">>" << a << " " << edges[a].a << " " << edges[a].b << "\n";
			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();
			unsafe.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:109:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  while(iq < qry.size() || ie < edg2.size()) {
      |        ~~~^~~~~~~~~~~~
bridges.cpp:109:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<EDG2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  while(iq < qry.size() || ie < edg2.size()) {
      |                           ~~~^~~~~~~~~~~~~
bridges.cpp:110:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<EDG2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     if(ie == edg2.size() || qry[iq].b > edg2[ie].c) {
      |        ~~~^~~~~~~~~~~~~~
bridges.cpp:164:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<EDG2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   while(iv < v.size() || ic < curr.size()) {
      |         ~~~^~~~~~~~~~
bridges.cpp:164:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   while(iv < v.size() || ic < curr.size()) {
      |                          ~~~^~~~~~~~~~~~~
bridges.cpp:166:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     while(ic < curr.size() && curr[ic].t == 1) {
      |           ~~~^~~~~~~~~~~~~
bridges.cpp:169:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<special>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     if(ic >= curr.size() || (iv < v.size() && v[iv].c >= curr[ic].c)) {
      |        ~~~^~~~~~~~~~~~~~
bridges.cpp:169:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<EDG2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     if(ic >= curr.size() || (iv < v.size() && v[iv].c >= curr[ic].c)) {
      |                              ~~~^~~~~~~~~~

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